# Prove that in a graph of 100 vertices each with degree $67$ a subset is $K_4$

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!

• Instead of 100 people and 67 each, with, say, 6 people, how many must each know to guaranteee a $K_4 \; ?$ – 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.