# Every $2$-coloring of $K_n$ contains a hamiltonian …

Every $2$-coloring of $K_n$ contains a hamiltonian cycle that is made out of two monochromatic paths.

If there is a monochromatic hamiltonian cycle then we are done. Elseway I thought about using Dirac's theorem somehow (I know that there is in both monochromatic induced subgraphs there is a vertex with degree higher than $n/2$).

• $K_n$ is the complete graph on $n$ vertices.
• A Hamiltonian cycle is a cycle that visits each vertex exactly once.
• A $2$-coloring of the graph is a partition of the set of edges in two sets (for example the "blue" edges and the "red" edges).
• Ok , if there is a monochromatic hamiltonian cycle then we are done. Elseway I though about using Dirac's theorem somehow (I know that there is in both monochromatic induced subgraphs there is a vertex with degree higher than $n/2$) – UserB95 Feb 15 '15 at 13:29
• Cute problem. No need to use Dirac's theorem or any other big result; instead, induction seems to be the way to go. – Tyler Seacrest Feb 16 '15 at 5:49
• @TylerSeacrest Sorry but I can't see how to use induction here... I tried throwing a general vertex with no success :P – UserB95 Feb 16 '15 at 9:44
• Hmm, I'll try writing up a proof and see if my induction idea works ... – Tyler Seacrest Feb 16 '15 at 22:36

Choose any vertex $v \in K_n$. Then $K_n \setminus v$ is a 2-colored copy of $K_{n-1}$, and thus by induction contains a Hamiltonian cycle that is the union of a red path and a blue path. Let $u$ be a vertex where these two paths meet, and let $r$ be $u$'s neighbor along the red path, and $b$ be $u$'s neighbor along the blue path.
Suppose $uv$ is colored blue. Then throw away $ur$ and instead use $uv$ and $vr$ in your Hamiltonian cycle (it does not matter what color $vr$ is). If $uv$ is colored red, then throw away $ub$ and use $uv$ and $vb$ in your Hamiltonian cycle. Either way, you've extended your Hamiltonian cycle to include $v$ and it is still the union of a blue and red path.
I've ignored the case where the Hamiltonian cycle in $K_{n-1}$ is monochromatic, but it is trivial to extend the cycle to $v$ in this case.