Existence of $K_3$ in a graph with $(n^2+1)$ edges 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.
 A: 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.
A: 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$.
