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?

  • $\begingroup$ 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$. $\endgroup$ – Quotable Jun 7 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.

  • $\begingroup$ Excellent! Thanks! Took some thought to grasp the last bit, but now I get it I appreciate the simplicity. $\endgroup$ – FreshmanMath Oct 14 '12 at 9:44
  • $\begingroup$ @FreshmanMath: You’re welcome. That one was fun. $\endgroup$ – Brian M. Scott Oct 14 '12 at 9:45
  • $\begingroup$ 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? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.