Prove that if G is k-regular with an odd number of vertices, then the edge chromatic number of G is k+1

Question

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!

Answer 1

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?

Answer 2

Assume there exists a proper $k$-edge colouring of $G$ which is $k$-regular and then number of vertices of $G$ i.e $v(G)$ is odd. Then the edge set of $G$ can be partitioned into $k$ sets $(E_1,E_2,.....E_k$) such that each set is a perfect matching .

Also since degree of every vertex is $k$, it has $k$ edges incident to it and all have different colours. Thus if $v$ is a vertex of $G$ then it should belong to every edge set $E_i$ since there is an edge incident to $V$ with color $i$.

Then each $E_i$ has all the vertices of $G$ ( which is odd in number) and is a perfect matching. This is a contradiction.

Thus G has edge chromatic number $k+1$.