# Graph theory: Prove $k$-regular graph $\#V$ = odd, $\chi'(G)> k$

I'm looking to prove that any $k$-regular graph $G$ (i.e. a graph with degree $k$ for all vertices) with an odd number of points has edge-colouring number $>k$ ($\chi'(G) > k$).

With Vizing, I see that $\chi'(G) \leq k + 1$, so apparently $\chi'(G)$ will end up equaling $k+1$.

Furthermore, as $\#V$ is odd, $k$ must be even for $\#V\cdot k$ to be an even number (required to be even, since $\frac{1}{2}\cdot\#V\cdot k = \#E$.

Does anyone have any suggestions on what to try?

• For future readers, be sure to note that for multigraphs, Vizing's theorem does not hold, so the only result you can guarantee is that $\chi'(G) > k$. For example, a triangle with each edge replaced with $k$ parallel edges has $\chi'(G) = 3k > k+1$. – Quotable Jun 7 '19 at 5:40

Let $G=\langle V,E\rangle$ be a $k$-regular graph with $n=2m+1$ vertices; as you say, clearly $k=2\ell$ for some $\ell$, so $G$ has $$\frac{kn}2=\frac{2\ell(2m+1)}2=\ell(2m+1)$$ edges. Suppose that $c:E\to\{1,\dots,k\}$ is a coloring of the edges of $G$. $$\frac{\ell(2m+1)}k=m+\frac12\;,$$ so there is some color that is used on at least $m+1$ edges. $G$ has only $2m+1$ vertices, so two of these edges must share a vertex, and $c$ therefore cannot be a proper coloring.
• I didn't quite understand the last part, "$c$ is a coloring of edges of $G$". Why is the colour used on at least $m+1$ edges? – user59036 Mar 7 '17 at 5:33
Another way to prove this fact is to notice that in any proper edge coloring, every set of edges that share a color must form a matching. But for any given color, the matching touches an even number of vertices, so there must be one vertex missing that color. Since that vertex has $k$ edges, all of a different color, together there must be at least $k + 1$ colors.