# Two-colourings of the complete graph on n vertices

The question is:

Show that there is a two-colouring of the complete graph $$K_n$$ on $$n$$ vertices with at most

$$\displaystyle {n \choose k} 2^{1-{k \choose 2}}$$

monochromatic subgraphs $$K_k$$.

(Hint: Compute expectation of the number of monochromatic $$K_k$$. )

I'm confused about what a two-colouring is. Diestel (Graph Theory) says a $$k$$-colouring is a vertex partition into $$k$$ independent sets. But for $$n \geq 2$$ I don't see how you can do this on $$K_n$$. Can someone work out what "two-colouring" means in this context?

If I assume it means colouring each edge one of two colours randomly, I can prove the result. But I don't see why it should mean this. It's just me doing what's easy.

Thanks!

• It could mean coloring each $\it vertex$ one of two colors. May 26, 2011 at 12:19
• It means coloring each edge one of two colors. (The other interpretation is clearly false.) May 26, 2011 at 12:22
• Why not just clarify with the instructor/professor? May 26, 2011 at 15:18
• Shouldn't the terminology of the problem then say 2-edge-coloring as the default is usually '... vertex ...' ? May 26, 2011 at 16:36

This appears in the classic probabilistic proof of existence of the Ramsey number $R(k,k)$, due to Erdos, and is indeed a colouring of the edges.