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?

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.
