Prove that among $ 9 $ people, there are $ 3 $ who know each other or $ 4 $ who do not know each other.

I began by trying to prove $ R_9 \rightarrow R_3, R_4 $. Let $ S $ be a set of $ 9 $ points in the plane, no three of which are collinear. Let the lines joining these points be coloured either red or blue (red denotes a relation, blue denotes none). Consider any one of the points and the $8$ line segments joining this point (say $ P $) with the other points on the plane. By the pigeon-hole principle, at least $4$ of them are either red or blue. WLOG assume four red lines meet the other points at $A$, $B$, $C$ and $D$ respectively. Consider the lines joining these points. If all of them are blue, then we have a blue $K_4$. If one of them is red, then we have a red $K_3$.

Is my reasoning correct?

I'm quite new to Ramsey's theorem and I'm still a high school sophomore so please answer accordingly so I can comprehend.


The one problem with your proof is your use of WLOG (without loss of generality) in saying "WLOG assume four red lines meet the other points...".

In this problem, the red and blue colors play different roles, so assuming that red is the dominant color on lines out of $P$ is a loss of generality. You would not be able to reproduce the same argument in the case where $P$ has four blue lines to $A$, $B$, $C$, and $D$. In that case, it's perfectly possible to color the lines between $A$, $B$, $C$, and $D$ without creating either a blue $K_4$ or a red $K_3$ using those four points and the original point alone. Even assuming that $P$ has five blue lines out of it is not enough!

To make the proof work, you need to exploit the asymmetry of the problem. Let $r$ be the number of red lines out of $P$, and let $b$ be the number of blue lines out of $P$. I suggest splitting the problem into cases as follows:

  1. $r \ge 4$.
  2. $b \ge 6$.
  3. $r=3$ and $b=5$.

One of these has to happen: we have $r+b = 8$, so either $r \ge 4$, or $r=3$ (making $b=5$) or $r \le 2$ (making $b \ge 6$).

You've handled the first case already, and the second case is not too much harder. In the third case, we seem to get stuck; however, you can show that the third case can't possibly hold for every choice of $P$: one of the points must fall into either case 1 or case 2. If you do, that will complete the proof.

| cite | improve this answer | |
  • $\begingroup$ Thank you for you help. How do I start for the third case? $\endgroup$ – alphasquared Oct 30 '17 at 8:04
  • $\begingroup$ Review the handshake lemma. $\endgroup$ – Misha Lavrov Oct 30 '17 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.