4
$\begingroup$

I'm trying to prove that there is a way to color (edges) a $K_{2t}$ graph with $t$ colors so it won't contain any monochromatic cycles.

I thought to display the graph as a disjoint union of $t$ paths ($P_{2t-1}$) (each path in different color, no same edges in each of the paths).

This work great in theory, the only thing I'm not sure of is if I can really create $t$ paths ($P_{2t-1}$). It sounds and seems good but how can I prove its right?

  • 0
    Here's an [MO post](http://mathoverflow.net/questions/60856/) solving the problem.2012-01-02

2 Answers 2

2

Maybe it's easier to start with $K_{2t+1}$, decompose it into cycles, then erase one vertex (and all the edges adjacent to it).

EDIT: Typing

complete graph decompose cycle

into Google turned up several encouraging links.

0

Gerry's approach is more elementary, but you can also use the Tutte-Nash-Williams Theorem, which says that a graph $G$ is the union of $t$ edge-disjoint forests if and only if for every subgraph on n' vertices and m' edges, the inequality m'\le tn' - t holds.

The statement to be proved is that $K_{2t}$ is the union of $t$ edge-disjoint forests, so we just check the condition given above. There are $2t$ vertices and $t(2t-1)$ edges, so the desired inequality holds as an equality for the whole graph. Moreover, since any induced subgraph is also a complete graph on fewer than $2t$ vertices, we see that the number of edges is \frac{1}{2}n'(n'-1) < t(2n'-1).