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

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.


share|cite|improve this question
It could mean coloring each $\it vertex$ one of two colors. – Gerry Myerson May 26 '11 at 12:19
It means coloring each edge one of two colors. (The other interpretation is clearly false.) – Qiaochu Yuan May 26 '11 at 12:22
Why not just clarify with the instructor/professor? – Aryabhata May 26 '11 at 15:18
Shouldn't the terminology of the problem then say 2-edge-coloring as the default is usually '... vertex ...' ? – Mitch May 26 '11 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.

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

share|cite|improve this answer

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.