Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|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
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|cite|improve this answer
Thanks for your answer! Seems so easy now :) – Daniel Dec 31 '11 at 19:28

Your Answer


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.