Team Selection Test for IMO 2009

We want to show that if $G-v$ has a Hamiltonian cycle for each vertex $v$ in a graph $G$, but $G$ does not have a Hamiltonian cycle, then $n=|G|\ge 10$, and produce such a graph $G$ with $n=10$.

Since $v$ cannot be adjacent with two consecutive vertices in a Hamiltonian cycle in $G-v$, we have $\mathrm{deg}v\le [(n-1)/2]$. On the other hand, if $\mathrm{deg}w\le 2$ for some vertex $w$, then there is no Hamiltonian cycle in $G-v$ where $v$ is vertex adjacent with $w$. Therefore $3\le \mathrm{deg}v\le [(n-1)/2]$. In particular, $n\ge 7$.

Next observe that if $v_1\to v_2\to \cdots \to v_{n-1}$ is a Hamiltonian cycle in $G-v$, and if $v$ is adjacent with $v_i$ and $v_j$, $i<j$, then $v_{i-1}$ and $v_{j-1}$ can not be adjacent with each other, as that would give a Hamiltonian cycle $v_1\to \cdots \to v_{i-1}\to v_{j-1}\to v_{j-2}\to \cdots \to v_i\to v\to v_j\to v_{j+1}\to \cdots \to v_{n-1}$ in $G$.

From these observations it follows that $n=7$ and $n=8$ are impossible. If $n=9$, then each vertex has degree 3 or 4, and they cannot all have degree 3 by the degree sum formula. Hence assume that $n=9$ and there is a vertex $v_0$ with $\mathrm{deg}{v}_0=4$.

Then $G$ must contain the graph on the left below.





But then, again from the observations above, it follows that each $v_{2i}$ must be adjacent with at least -and therefore exactly- one of $v_{2i+3}$ and $v_{2i+5}$ (indices considered mod 8), and there are no other edges. Since there are edges only between vertices of different parity in the resulting graph; if we remove an odd indexed vertex, the remaining graph cannot have a Hamiltonian cycle as it has unequal number of odd and even indexed vertices.



In this graph, $a\to c\to C\to B\to b\to e\to E\to D\to d\to a$ and $A\to B\to C\to c\to e\to b\to d\to D\to E\to A$ are Hamiltonian cycles for $G-A$ and $G-a$, respectively.

$G$ itself does not have a Hamiltonian cycle. A Hamiltonian cycle cannot contain exactly two of the edges $Aa$, $Bb$, $Cc$, $Dd$, $Ee$, as there are no adjacent pairs of vertices on the outer and the inner cycles. So it must contain exactly four of them; say, $Bb$, $Cc$, $Dd$, $Ee$. Then the cycle contains a path through $b$, $B$, $A$, $E$, $e$, and a path through $C$, $c$, $a$, $d$, $D$; and these two paths cannot be completed to a Hamiltonian cycle.