Looking to show that $\forall n \in \mathbb{N}$


I'm trying to construct a colouring of the edges of $K_{2n+1}$ that leaves colour $i$ missing at vertex $i$ so I can move to $K_{2n+2}$ without increasing the index (for my induction) but the details of that initial colouring are hard to work out.


I agree with Leen that induction might not be the way to go. But still, most proofs on the colorability of $K_n$ do not construct an explicit coloring. I think it's worth it to construct one at least once, so here goes :)

Say your vertex set is $V = \{0, 1, \ldots, n - 1\}$ with $n$ odd.

Color the edge $\{i, j\}$ with color $i + j$ (mod $n$). You should be able to show that no vertex has two incident edges of the same color.

Now, one needs to show that each vertex in this coloring misses a distinct color. This'll show that $K_{n + 1}$ can be colored with $n$ colors, $n + 1$ being even.

Actually, vertex $i$ misses color $2i$ (mod $n$). For otherwise, there are distinct $i, j$ such that $i + j \equiv 2i$ (mod $n$). This implies that either $j = i$ or $j = n + i$, the two of which are not possible. All that remains for you to show is that for distinct $i, j$, $2i \not \equiv 2j$ (mod $n$), and hence that all vertices have a distinct color they're missing.


You probably should not use induction.

Vizing tells you that $\chi'(K_k)$ is either $k-1$ or $k$. If $\chi(K_k)=k-1$ every color appears at every vertex, so the edges of one color form a perfect matching, which implies that $k$ must be even.

You said you could handle the other part? (The other part is proved if you know, or can prove, that for odd $k$ $K_k$ has a decomposition in Hamiltonian cycles. Let me know if you don't know how to do this. It is not hard.)

  • $\begingroup$ I've been to all the lectures and I'm pretty sure Vizing's theorem is all we've got for edge colourings - in particular factors of a graph have not been defined $\endgroup$ – John Fernley Mar 2 '15 at 16:05
  • $\begingroup$ One of the other questions I can't do though is about a 3-regular graph $G$ with $\chi^{'}(G)=3$ and a unique 3-edge colouring having exactly 3 Hamilton cycles which also seems close to the factorization idea, so I'll read into it $\endgroup$ – John Fernley Mar 2 '15 at 16:07
  • $\begingroup$ The other direction is ok but I still have problems with this direction. For a start you have the index off by one in Vizing's theorem, but why "if there is a k-edge-coloring of $K_k$ every edge color must appear at each vertex"? $\endgroup$ – John Fernley Mar 2 '15 at 18:12
  • $\begingroup$ I see that this would be true for a 1-factorisation with $\chi^{'}(K_k)$ factors but not for an optimal colouring (are these equivalent in general?) $\endgroup$ – John Fernley Mar 2 '15 at 18:13
  • 1
    $\begingroup$ No, it does not just have to do with the 'degree of regularity'. So there are 3-regular graphs $G$ with $\chi'(G)=3$ (like $K_4$), but there are also 3-regular graphs that require 4 colors (like the Petersen graph). $\endgroup$ – Leen Droogendijk Mar 2 '15 at 18:44

Just another solution: Label the vertices $1,2,\ldots, 2n+1$ and for each $i$, colour edge $(i+k,i-k)$ using colour $i$ for every $k=1,2,\ldots,n$ (operations modulo $2n+1$). This is a proper edge colouring using $2n+1$ colours with the property that no edge coloured $i$ is incident to vertex $i$.

Example for $2n+1=7$:

enter image description here

  • $\begingroup$ Actually it's the same colouring "pattern" as Manuel's answer, but with vertices relabelled. $\endgroup$ – Casteels Mar 3 '15 at 11:40

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.