Hamiltonian cycle
Task number: 4020
Show that if we arbitrarily color the edges of a complete graph on at least three vertices with two colors, then we can always find a Hamiltonian cycle such that it is either completely monochromatic or its edges can be divided into two monochromatic paths.
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).
