Problem: (Adrian Tang)
$G$ is a graph with $2n+1$ vertices. In $G$, for every set $S$ of at most $n$ vertices, there is one vertex outside of $S$ that is adjacent to every vertex in $S$.
Prove that at least one vertex is adjacent to every other vertex.
My approach: assume for contradiction that the vertex of highest degree doesn't have degree $2n$. There is something about its neighbourhood that arouses a contradiction that there is a vertex with a higher degree.
Say a graph $M$ is complete if every vertex in $M$ is connected to each vertex $M$. Note that such graph exist (say with $2$ vertices).
Take maximal complete subgraph $M$. If size of this grraph $M$ is $k\leq n$ then there is some vertex connected to each vertices in $M$. So we can add it to this graph and we get new complete graph $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$ vertices, so there is some vertex in $M$ which is connected to all in $M^C$. But then this one is connected to each vertex.