In a waiting room, there are $100$ people, each of whom knows $67$ others among the $100$.

Prove that there exist $4$ people in the waiting room who all know each other (that is, each knows the other $3$).

Progress: I have restated it in graph theoretic terms as the title says. Now, consider the following coloring of this graph: if two people know each other than the edge is colored red. Otherwise, the edge is colored blue. There are $\dfrac{67\cdot100}{2}$ red edges, and $\dbinom{100}{2}$ total edges. This means that there are $1600$ blue edges. Now, consider four vertices, $A, B, C, D$. We wish to prove that the complete graph for these four vertices is not entirely red. This means that there must be a blue edge in every $K_4$. It suffices to prove that this condition implies more than 1600 blue edges.

However, I don't know how to proceed from here. Any help would be appreciated!

  • $\begingroup$ Instead of 100 people and 67 each, with, say, 6 people, how many must each know to guaranteee a $K_4 \; ?$ $\endgroup$
    – Will Jagy
    Oct 3 '17 at 0:30

Each person knows $67$ other people, and does not know $32$ of the people there.

So let us pick one person, $A$, and look at the $67$ people $A$ knows and pick one of those, $B$. Now $B$ is only a stranger to $32$ people so $B$ knows at least $66-32=34$ of the same people that $A$ knows. Pick one of these people that both $A$ and $B$ know, $C$, and again $C$ must know at least $33-32=1$ of the other people that $A$ and $B$ know, giving a set of four people that all know each other.

Note that this is far stronger than the original requirement. This shows that for any two people in such a group that know each other, there are two other people that they both know and who know each other.


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.