## Hamiltonian cycle

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