3
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ 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$) $\endgroup$ – UserB95 Feb 15 '15 at 13:29
  • 1
    $\begingroup$ Cute problem. No need to use Dirac's theorem or any other big result; instead, induction seems to be the way to go. $\endgroup$ – Tyler Seacrest Feb 16 '15 at 5:49
  • $\begingroup$ @TylerSeacrest Sorry but I can't see how to use induction here... I tried throwing a general vertex with no success :P $\endgroup$ – UserB95 Feb 16 '15 at 9:44
  • $\begingroup$ Hmm, I'll try writing up a proof and see if my induction idea works ... $\endgroup$ – Tyler Seacrest Feb 16 '15 at 22:36
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yeah I had a mistake , it really does't matter what vb and vr are , thanks =D $\endgroup$ – UserB95 Feb 16 '15 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.