I have a following problem.
There are $2n+1$ people in the room. For any group of $n$ people there is a person (different from them) who is friends with each person in this group. Prove that there is a person, who knows all $2n$ other people.
One can easily see, that $\min_v \deg v = n$. From this we can get a lower bound for number of edges $N_e$:
$$
N_e = \frac{1}{2}\sum_v \deg v \geq \frac{(2n+1) \cdot n}{2}
$$
I do not know where to move from this point (and do not think, that this is the right direction) and pretty stuck right now. Can you give a hint?
Best Answer
Say a group $M$ is good if everyone in $M$ knows everyone in $M$. Note that such group exist (say with $2$ people).
Take maximal good subgroup $M$. If size of this group $M$ is $k\leq n$ then there is somebody who knows them all. So we can add him to this group and we get new good group $M'$ which is bigger then $M$. A contradiction. So $M$ is of size $k\geq n+1$. Then in $M^C$ we have at most $n$ people, so there is somebody in $M$ who know everybody in $M^C$. But then this one knows everybody.