[Math] Prove that at a party of $25$ people there is one person knows at least twelve people.

Question

So, the full problem goes like this:

There are $25$ people at a party. Assuming that among any three people, at least two of them know each other, prove that there exists one person who must know at least twelve people.

I've been stuck on this problem for a while and haven't really figured out how to proceed. I'm pretty sure that there is an answer that can be found via the pigeonhole principle or some graph theory, but I'm not really sure how to get started. Any help would be appreciated.

Answer 1

If everyone knows everyone, then you are done.

Otherwise choose two people, A and B say, who don't know each other. These two people are part of $23$ triples. In each of these triples, either A knows the third person, or B knows the third person.

Thus one of A or B knows (at least) $12$ people.