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?

  • 1
    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" :)2011-12-31
  • 1
    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).2011-12-31
  • 1
    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.2011-12-31
  • 2
    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.2011-12-31
  • 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)$.