Let be a connected Graph.
If is not an odd cycle or a complete graph then
Proof
First is regular by ordering vertices and greedy colouring
If is not connected, consider the cut vertex
and let be a component of together with
Then colour those components and combine
If is connected, pick
Pick such that are not connected
Then form the path and use greedy