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).

Difficulty level: Moderate task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email