1
$\begingroup$

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!

  • 0
    yea it was, thanks!2011-12-31

1 Answers 1

3

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!

  • 0
    Thanks for your answer! Seems so easy now :)2011-12-31