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 $\deg v \le [(n-1)/2]$. On the other hand, if $\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 \deg v \le [(n-1)/2]$. In particular, $n \ge 7$.

Next observe that if $v_1 \to v_2 \to \dots \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 \dots \to v_{i-1} \to v_{j-1} \to v_{j-2} \to \dots \to v_i \to v \to v_j \to v_{j+1} \to \dots \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 $\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.