# In a club with 99 people, everyone knows at least 67 people. Prove there's a group of 4 people where everyone knows each other

I tried solving this with graph theory. So there are 99 points (each point is a person) and if we draw a line between two points, it will mean those two people knows each other (Since knowing someone is mutual).

So, there are at least $$\frac{99*67}{2}$$ lines and we need to prove there's at least a group of four points where every point is connected with the other three.

Directly, i don't know how to prove it, since there are $$\frac{99*98*97*96}{6}$$ possible groups of four points, but i don't find anything with this.

So i also tried to see how many groups of three points where all three are connected, because, if another point is connected to these, it will be the group of 4 we're looking for. For this, if we select one point $$A$$, it will connect with at least 67 points, then, we select one $$B$$ of those 67. It will connect with at least 66 besides $$A$$. If we want to have the less posible amount of triangles, then we have to connect $$B$$ with the points that aren't connected with $$A$$, and these are 31, but $$B$$ will have to connect with at least other 36, so there are at least 36 triangles. Now, this only used $$A$$ and $$B$$ so there are way more triangles but i don't know how to proceed.

Any suggestions or ideas?

You have shown that $$A$$ and $$B$$ have at least $$35$$ mutual acquaintances. Let $$C$$ be one of them. If $$C$$ knows any of the other $$34$$, then we have a group of four who all know each other. In order to avoid such a group, $$C$$ can know at most $$98-34=64$$ members (including $$A$$ and $$B$$), but it is given that $$C$$ knows at least $$67$$ members.
You can also use the Turan theorem. Suppose there is no such 4, then there is at most $${99^2\over 3}$$ acquaintances. But on the other hand we have by handshake lemma at least $${99\cdot 67\over 2}$$ acquaintances.
So we have $${99\cdot 67\over 2} \leq {99^2\over 3} \implies 67\cdot 3\leq 99\cdot 2$$