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!