I want to prove that a simple graph that is 3-regular and has edge chromatic index 4 does not have a Hamiltonian cycle.
After some research, I have found that the Petersen graph fits the criteria and can be seen as an example of a 3-regular, 4-edge-chromatic, simple graph that does not have a Hamiltonian cycle. However, I am having trouble generalizing the proof without using the Petersen graph. Any thoughts?
Best Answer
If a graph is $3$-regular then it has an even number of vertices.
Assume the graph has a hamiltonion cycle, we can color the edges of that cycle in an alternating fashion using your two favorite colors, which are red and blue.
If we only consider the edges that do not pertain to the cycle we get that every vertex has degree $1$, hence the graph is a perfect matching, we can color these remaining edges green and get an edge-coloring in which every vertex has exactly one edge of each color. Therefore a $3$-regular graph with a hamiltonian cycle can be edge-colored with $3$ colors.