Team selection tests for GMO 2018

Let $V$ denote the set of all vertices. Let $d$ be the greatest degree of a vertex in the graph and $v\in V$ be a vertex with degree $d$ and let $D\subset V$ be the set of $d$ vertices connected to $v$.

In the full subgraph consisting of vertices in $D$, no vertex can have degree 2 or more, because this would make a cycle of length 4. Therefore, there are at most $\lfloor \frac{d}{2}\rfloor$ edges in this full subgraph.

Similarly, none of the $7-d$ vertices in $V\setminus (D\cup \{v\})$ can have 2 or more connections to $D$ because this would also make a cycle of length 4. Therefore, there are at most $7-d$ edges between $V\setminus (D\cup \{v\})$ and $D\cup \{v\}$. Finally, the number of edges in $V\setminus (D\cup \{v\})$ is at most $\left(\genfrac{}{}{0ex}{}{7-d}{2}\right)$, hence $$e\le d+\lfloor \frac{d}{2}\rfloor +7-d+\left(\genfrac{}{}{0ex}{}{7-d}{2}\right)=7+\lfloor \frac{d}{2}\rfloor +\left(\genfrac{}{}{0ex}{}{7-d}{2}\right)$$ - If $d\ge 5$, $e\le 7+\lfloor \frac{d}{2}\rfloor +\left(\genfrac{}{}{0ex}{}{7-d}{2}\right)\le 10$. - If $d=4$, $e\le 7+\lfloor \frac{4}{2}\rfloor +\left(\genfrac{}{}{0ex}{}{7-4}{2}\right)=12$. - If $d\le 3$, $e=\frac{{\sum }_{u\in V}d(u)}{2}\le \frac{8\cdot 3}{2}=12$.

Let us now prove that $e=12$ is not possible by ruling out the two cases with $d=4$ and $d=3$.

1. If $e=12$ and $d=4$, then there are exactly 2 edges in the full subgraph consisting of vertices in $D$ (each vertex in $D$ is connected to exactly one other vertex in $D$), there are exactly 3 edges between $V\setminus (D\cup \{v\})$ and $D$ (each vertex in $V\setminus (D\cup \{v\})$ is connected to exactly 1 vertex in $D$) and there are exactly 3 edges in $V\setminus (D\cup \{v\})$ (all 3 of the vertices in $V\setminus (D\cup \{v\})$ are connected).

Let us denote the vertices in $V\setminus (D\cup \{v\})$ by $a_1,a_2,a_3$. $a_i$ and $a_j$ cannot be connected to the same vertex in $D$, otherwise this would make a cycle of length 4 (for example $(a,c,b,x)$ cyclically connected).

Therefore, exactly 3 of the 4 vertices in $D$ are connected to $V\setminus (D\cup \{v\})$. Since each vertex in $D$ is connected to exactly one other vertex in $D$, two of these 3 vertices are connected. Let us call them $x,y$ and let us assume without loss of generality that they are connected to $a_1$ and $a_2$. Now, we have a cycle of length 4 as $(x,y,a_2,a_1)$ are cyclically connected. Therefore, $e=12$ and $d=4$ is not possible.

2. If $e=12$ and $d=3$, then all vertices in the graph must have degree 3. Let $v$ be any vertex and $D$ be defined as above. Similarly as above, no vertex in $V\setminus (D\cup \{v\})$ can have 2 or more connections to $D$ as this would make a cycle of length 4.

Hence, each vertex in $V\setminus (D\cup \{v\})$ is connected to at most 1 vertex in $D\cup \{v\}$ and thus connected to at least 2 vertices in $V\setminus (D\cup \{v\})$. If we consider the full subgraph consisting of the 4 vertices in $V\setminus (D\cup \{v\})$, each vertex has degree at least 2. In a graph with 4 vertices such that each vertex has degree at least 2, there must be a cycle of length 4. Therefore, $e=12$ and $d=3$ is also not possible.



Let us now give an example of a graph with $e=11$. Consider an octagon $ABCDEFGH$. Now, draw the additional three edges $AC,CE,EG$. This is a graph with 8 vertices, 11 edges and no cycles of length 4.