Let $n$ be a positive integer. In a group of $2n + 1$ people, each pair is classified as friends or
strangers. For every set $S$ of at most $n$ people, there is at least one person outside of $S$ who is friends with everyone in $S$. Prove that at least one person is friends with everyone else.
For every set S of at most n people, there is at least one person outside of S who is friends with everyone in S.
graph theory
Best Answer
Take two disjoint sets of $n$ persons $A$ and $B$ such that the number of friendships between $A$ and $B$ is the minimum possible. Suppose that call the remaining dude $x$ and suppose that $x$ doesn't know everyone in $A$. Notice that if we swap the dude in $B$ that knows everyone in $A$ with $x$ we get even less friendships between $A$ and this new set. Hence we conclude $x$ knows everyone in $A$ and analogously $x$ knows everyone in $B$