Graph theory/pigeonhole question.

Question

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 know the other 3). You assume that knowing is mutual (if A knows B, then B knows A).

I understand that if there are 4 people in the waiting room who all know each other, that makes K_4, or a connected graph. However, the "67 others among the 100" part stumps me. Can someone give a hint/hints? Please do not solve the problem for me or give me the answer. I only need a hint/hints to get me started.

Thanks for all of your help!!

Answer 1

Here the hint you want:

You're trying to find 4 people who know each other? Well, take one person at random, and ask yourself "where can I find the second person?", and you when you find the 2°, ask "where can I find the third?", and the same for the fourth.

Bonus You can try to prove a stronger question: prove that for every three people that know each other there exists a person that knows all of them

Answer 2

Another way you can do it is by letting this be a graph since you tagged this problem graph theory.

Consider the waiting room as a a graph, where each vertex corresponds to a member, and a pair of vertices is connected by an edge if the corresponding members know each other. So the degree of every vertex is between $67$ and $99$ inclusive, so there are $33$ different possible degrees. We need to show that $4$ vertices have the same degree.