Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 $\#V\cdot k = \frac{1}{2} \cdot \#E$.

Does anyone have any suggestions on what to try?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Excellent! Thanks! Took some thought to grasp the last bit, but now I get it I appreciate the simplicity. – FreshmanMath Oct 14 '12 at 9:44
@FreshmanMath: You’re welcome. That one was fun. – Brian M. Scott Oct 14 '12 at 9:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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