Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
This complements your previous question. Can you clarify if this is homework? If so, then add the [homework] tag. –  Srivatsan Dec 31 '11 at 21:58
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" :) –  Daniel Dec 31 '11 at 22:03
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). –  Ross Millikan Dec 31 '11 at 22:13
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. –  Daniel Dec 31 '11 at 22:25
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. –  Louis Dec 31 '11 at 23:45

2 Answers 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.