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

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.

Solution 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.

Solution 2:

Pick a vertex $v$. If $\deg(v) \geq 12$ you are done.

Otherwise $v$ is connected with at most 11 vertices. Let $C$ be the vertices connected to $v$ and $N$ be the vertices not connected to $v$. Note that $N$ has at least $13$ vertices.

Fix one vertex $u \in N$.

Now, for each $w \in N$ look at the group $\{ u, v, w\}$. The only possible edge in this group is $uw$. Therefore, $uw \in E(G)$.

This shows that $u$ is connected to all the other vertices in $N$.

Note The proof is basically the following:

The given condition shows that if you fix one vertex $v$, and you look to all the vertices $N$ which are not connected to $v$, then the induced graph on $N$ is the complete graph.

So if $|N| \geq 13$ you are done, otherwise $|N| \leq 12$ which means $\deg(v) \geq 12$.

Solution 3:

This one could be done also by Mantel–Turán theorem:

The maximum number of edges in an $n$-vertex triangle-free graph is ${\displaystyle \lfloor n^{2}/4\rfloor .}$

Let $G$ be a graph with $25$ vertices and connect two people iff they don't know each other. Suppose no one knows $12$ people, then the degree of each vertex is at least $13$ and thus the number of all edges is $\varepsilon$ where

$$ 2\varepsilon = \sum _{i=1}^{25} d_i \geq 25\cdot 13 \Rightarrow \varepsilon \geq {25\cdot 26\over 4}$$

But since this graph is triangle free we have $ \varepsilon \leq {25^2\over 4}$. A contradiction.

Solution 4:

Proof.

Choose two people $P_1$ and $P_2$ who do not know each other (if you cannot, we are done anyway). Now any third person $P$ either knows $P_1$ or $P_2$, because $\{P,P_1,P_2\}$ forms a group of three people and $\{P_1,P_2\}$ cannot be the pair knowing each other. There are $23$ such other people $P$. So by the pidgeonhole principle one of $P_1$ and $P_2$ must know at least $\lceil 23/2\rceil=12$ of them. $\quad\square$