I would like to show the following:

Show that if a regular graph with degree 3 has a Hamiltonian cycle, then it has an edge colouring with three colours.

Is it correct to use the following reasoning:

  1. Since it has a maximum degree $k$, then at least $k$ colours are needed for an edge colouring of $G$
  2. (unsure) It seems that such a graph has to be bipartite. In this case, it's simple to use a theorem that states that the minimum colours needed is equal to max degree of $G$, i.e. in our case it's $3$.

Does the 1st statement give a lower bound or the minimum numbers of colours needed. Is the 2nd statement stronger?

Are there better ways of showing this statement?

  • $\begingroup$ Such a graph does not have to be bipartite. The complete graph $K_4$ is a counterexample. $\endgroup$ – bof Oct 14 '16 at 9:11

By the handshaking lemma, the 3-regular graph must contain an even number of vertices, so the Hamiltonian cycle must be of even length; colour the edges of this cycle alternating two of the three colours. The remaining edges form a perfect matching in the graph; colour these edges with the third colour.

The image below shows this procedure applied to such a cubic Hamiltonian graph, the Dyck graph.

3-edge-colouring of the Dyck graph


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.