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.


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

1 Answer 1


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.

The wiki page on the probabilistic method has the proof here.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .