Collection of Maths Problems

Hamiltonian cycle

Task number: 4020

• Hint

  Use induction by the number of vertices.

• Solution

  For $C_3$ the statement follows by a straightforward analysis of two cases.

  Assume that the statement holds for $n-1$. From the graph $K_n$ we remove any vertex $u$ and in $K_n \setminus u$ we find a suitably colored Hamiltonian cycle. If monochromatic, adding $u$ to any point in the loop will create at most one blue segment, which would be the Hamiltonian cycle sought in $K_n$.

  Suppose, therefore, that the Hamiltonian cycle in $K_n \setminus u$ consists of two monochromatic segments and that $in$ is one of two vertices lying on the boundary of both colors (say red and blue). If the edge $(u, v)$ is red, $u$ can be inserted into the cycle between $v$ and its ‘blue neighbor’ to get the cycle we are looking for (and vice versa when edge $(u, v)$ is blue).