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