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

• Is knowing symmetric. I.e., if A knows B, can we be sure that B knows A? Sep 13, 2017 at 14:47
• @paw88789 yes $\,$ Sep 13, 2017 at 14:48

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.

• brilliant! $\,$ +1 Sep 13, 2017 at 15:02
• And that is indeed a Pigeonhole proof. You can put 22 triples into two pigeonholes such that there are only 11 in each, but the 23rd forces one of them to 12 Sep 13, 2017 at 18:35

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

• Also, this lets you construct a party of $24$ people easily - the union of two complete graphs of size $12$ (or the complement of $K_{12,12}$.) Sep 13, 2017 at 15:03
• Please note in your answer that this argument shows that there is not just one but at least $13$ vertices of degree $\ge12.$ I.e., either all vertices have degree $\ge12,$ or else there is a complete graph on $13$ vertices.
– bof
Sep 20, 2017 at 9:29
• This answer is much better (simpler and proves more) than the topo voted answer.
– bof
Sep 20, 2017 at 9:31

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$

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

The maximum number of edges in an $n$-vertex triangle-free graph is $\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.

Let A is the person who knows 12 people. Now, if there are 12 pairs (12*2) and the A is the third person then A knows at least one of them (pairs) So A knows 12 persons. :)

• Did you make a typo somewhere? The first sentence in your argument already assumes the claim is true! Sep 13, 2017 at 19:27