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!
Best Answer
We need at least $k$ colors because the $k$ edges meeting at a vertex must all have different colors. If we have a proper edge-coloring with exactly $k$ colors, then each vertex must be incident with edges of all $k$ colors, or in other words, each color must hit all the edges. So if red is one of the colors, then the red edges must cover all the vertices. Since each edge covers two vertices, if no two red edges share a vertex, then the red edges will cover an even number of vertices. Since the number of vertices is odd, it's impossible to cover all of the vertices this way.
This proves that the edge chromatic number is at least $k+1.$ Showing that $k+1$ colors are enough will be harder. Can we quote Vizing's theorem, or do we have to prove it from scratch? What can we use here?