Hamiltonian graph coloring

Question

Consider a graph that we know is completely connected and has a Hamiltonian cycle. Can we say that it is two colorable because we visit each vertex once and alternate colors as we walk the cycle? Or is this there something that I'm overlooking?

Answer 1

You can't conclude that.

First, because the graph might have an odd number of vertices, so that the cycle itself might require three colors.

And second, because two vertices of the hamiltonian cycle might be connected by an edge that is not part of the cycle, and in such a case you may not color those two vertices the same color.

To see the first thing, consider the triangle:

Clearly there is a hamiltonian cycle, and just as clearly, the graph requires three colors.

To see the second thing, consider this graph:

You want to color the vertices of the cycle red-blue-red-blue, but this makes $A$ and $C$ the same color, which is not allowed, because they are connected by an edge.

The answer of ml0105 is also to the point. The graph $K_n$ has a hamiltonian cycle, but cannot be colored with fewer than $n$ colors.

Answer 2

The Hamiltonian Circuit itself is at most three-colorable. Consider if there are an odd number of vertices. We know that $C_{2n+1}$ is three-colorable, for all $n > 0$. The original graph itself may not be three colorable, however. Consider $K_{10}$. It clearly has a Hamiltonian circuit, but is 10-colorable.