4
$\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$
4
  • $\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, 2015 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$ Feb 16, 2015 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, 2015 at 9:44
  • $\begingroup$ Hmm, I'll try writing up a proof and see if my induction idea works ... $\endgroup$ Feb 16, 2015 at 22:36

1 Answer 1

5
$\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$
1
  • $\begingroup$ Yeah I had a mistake , it really does't matter what vb and vr are , thanks =D $\endgroup$
    – UserB95
    Feb 16, 2015 at 23:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .