Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 3 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|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

 
discard

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.