I'm trying to prove that if G is k-regular with an odd number of vertices, then the edge chromatic number of G is k+1. Can someone give an idea of where to start a formal proof for this. I get the general idea that any k-regular graph will have k+1 edge colors. I've drawn out a bunch of examples. I'm just confused how to do a formal proof for this.
So far I have: In a k-regular graph, if there are an odd number of vertices, then each vertex must be of even degree in order to get an even degree sum. If each vertex is of even degree, the there is an even number of edges k coming out of each vertex. (I'm not sure where to go from here. I know if each vertex is of even degree there is a Euclidean circuit - could this fact help? Or is there some other way to complete the proof?)
Thanks for the help!