Existence of $K_3$ in a graph with $(n^2+1)$ edges

Question

I was working on this problem for quite a long time and was unable to solve it. Any help will be appreciated.

Let $G$ be a graph with $2n$ vertices ($n \in \mathbb{N})$ and $n^2+1$ edges. Show that there exist three vertices $v_1, v_2, v_3$ which are all mutually connected.

My progress: Let $v$ be the vertex with the highest degree. Note that $\deg (v) \geq 3$. If any two of the vertices connected to $v$ are mutually connected, we are done. Otherwise, we have three mutually disconnected vertices. I have no idea how to proceed from here, any help will be appreciated.

Thanks in advance!

I also tried considering the complement graph. It has $\dbinom{2n}{2}-(n^2+1) = n^2-n-1$ edges, and if the problem statement weren't to hold, no three mutually connected or mutually disconnected vertices. I can't find out how to utilize this idea though.

Answer 1

This is a special case of Turan's theorem, which states that a simple graph $G$ on $v$ vertices that does not have $K_{r+1}$ as a subgraph has at most $$e = \frac{r-1}{r} \frac{v^2}{2}$$ edges. For your question, $r = 2$ and $v = 2n$ and the result immediately follows. A proof of Turan's theorem therefore furnishes a proof of your claim.

Answer 2

Note that by convexity $$\begin{align}\sum_{uv\in E} (\rho(u)+\rho(v))&=\sum _{v\in V}\rho(v)^2\\&\ge (2n-2)n^2+2(n+1)^2\end{align}$$ where equality holds iff $2n-2$ vertices have $\rho(v)=n$ and the other $2$ vertices have $\rho(v)=n+1$. We transform further $$ \begin{align}(2n-2)n^2+2(n+1)^2&=2n^3+n^2+4n+2\\&=(2n+1)(n^2+1)+2n+1\\ &>(2n+1)\cdot |E|,\end{align}$$ hence by pigeon-hole there exists an edge $uv$ with $\rho(u)+\rho(v)\ge 2n+2$. This counts the edge $uv$ exactly twice so that there are at least $2n$ edges $xy$ with $x\in\{u,v\}$ and $y\notin\{u,v\}$. As there are only $2n-2$ vertices $\notin\{u,v\}$, pigeon-hole tells us once again that some $y$ must occur repeatedly, so that we have three mutually connected vertices $u,v,y$.