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 need help in the following question:

I need to prove that in all possible coloring with $t$ colors of the complete graph $K$ with $2t+1$ vertices, there will always be a monochromatic cycle (its size doesn't matter).

I tried with induction on number of colors ($t$) but got nowhere.

Any help would be welcome. :)

Thanks!

share|improve this question
    
By circle do you mean cycle? One of the colors appears three times, so you have a monochromatic triangle even. –  Louis Dec 31 '11 at 19:04
    
Daniel: I replaced the word "circle" by "cycle" everywhere since that seemed to be the intended term. Hope it's ok, –  Srivatsan Dec 31 '11 at 19:22
    
yea it was, thanks! –  Daniel Dec 31 '11 at 19:26
add comment

1 Answer

up vote 3 down vote accepted

Use the probabilistic method.

The number of edges in $K_{2t+1}$ is $\frac{2t(2t+1)}{2} = t(2t+1)$, so the average number of edges in a color class is $2t+1$. Hence there exists a monochromatic subgraph with at least $2t+1$ edges; this subgraph necessarily contains a cycle. Done!

share|improve this answer
    
Thanks for your answer! Seems so easy now :) –  Daniel Dec 31 '11 at 19:28
add comment

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.