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?