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:
- Since it has a maximum degree $k$, then at least $k$ colours are needed for an edge colouring of $G$
- (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?
Best Answer
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.