# Edge coloring $K_{2t}$ graph with $t$ colors so it won't contain monochromatic cycle

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?

-
These actually questions from tests from previous years. I'm studying for my own test now in less than a week and this is one of the questions I marked as "help needed" :) – Daniel Dec 31 '11 at 22:03
Already $K_4$, which has $6$ edges, cannot be divided into two disjoint paths. You can get one triangle and one tree with three branches, but if you color each with one color you get a monochromatic cycle. For $K_4$ you need $AB, BC, CD$ to be one color and $AC, BD, AD$ the other (or something like that). – Ross Millikan Dec 31 '11 at 22:13
Ross, this actually does work for $K_{4}$. If we have $K_{4}$ then t=2. You can make 2 paths: 1) AB,BD,DC 2) DA,AC,CB . Combining these 2 will give you $K_{4}$ with no monochromatic cycle. Maybe I didn't make it clear, when I said disjoint union of paths, I meant only their edges to be different, not vertices. – Daniel Dec 31 '11 at 22:25
A heavy answer is to check that the hypotheses of the Tutte-Nash-Williams Theorem is met, so you can decompose it into $t$ trees. – Louis Dec 31 '11 at 23:45
Here's an MO post solving the problem. – Srivatsan Jan 2 '12 at 3:19

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

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)$.