Induction works. Assume we have shown the result to be true for small $n$. Suppose we are given $2(n+1)$ points with $(n+1)^2+1$ edges between them. By Turan's Theorem, there is a triangle. This means that we can choose two vertices $x,y$ of the triangle with degrees of the same parity. They are, of course, connected, since they form a side of the triangle. If the other $2n$ points have $n^2+1$ sides between them, then we're done by the induction hypothesis. If, on the other hand, they do not, there are at least $2n+2$ edges adjacent to either $x$ or $y$. One of these edges is between the two, and there can't be only $2n+1$ more because the degrees of $x,y$ have the same parity. This means that there are at least $2n+2$ edges adjacent to either $x$ or $y$ but not both. From here we easily conclude that $x,y$ have at least two common neighbours $u,v$, and $x,y,u,v$ is the "$K_4-$ one edge" .

Strange...I'm quite sure to have seen that one before but I can't find it anymore Pierre.

Almost same as grobber' s solution: With induction on $ n$. For $ n=2$ it is obviously. Now let graph $ G$ have $ n^{2}+2n+2$ edges and $ 2n+2$ vertices. By Turan' s theorem $ G$ contains $ K_{3}$. If some node from the $ G'=G\setminus K_{3}$ is connected to two vertices form $ K_{3}$ we are done. Now let us assume that every vertices from $ G'$ is connected to at most one vertices from the set $ K_{3}$. So in the set $ G'$ we have at least $ n^{2}$ edges and exactly $ 2n-1$ vertices. Here is tricky part which I don't know if it is correct. Let us add to $ G'$ artificial node which is connected with exactly one node from $ G'$. Then new graph has $ n^{2}+1$ edges and $ 2n$ vertices. By induction it has $ H=K_{4}$-edge and artificial node is not on it since it has degree 1. So $ G'$ contains $ H$ and so does $ G$ and we are done. I hope this with artificial node works.

Is this right? It seems a little strange. We proceed using induction, with the base case of $n=2$ trivially true. Suppose that $n>3$ and some edge $v-w$ is not a part of a triangle. Then, $v$ and $w$ have no common neighbors, so $\deg v+\deg w\le 2n$. Removing $v$ and $w$ results in a graph with $2(n-1)$ vertices and at least $n^2+1-(2n-1)=(n-1)^2+1$ triangles, and we are done by the inductive hypothesis. Otherwise, every edge must be part of a triangle. If the problem is false, then each edge must in fact be a part of exactly one triangle. But as we have $n^2+1$ edges, we must then have $\frac{n^2+1}{3}$ triangles, a contradiction as that is not an integer for any $n$. Thus, there exists an edge that is a part of two triangles, as desired.

The case of $n=2$ is obvious, as any graph on $4$ vertices with $5$ edges is just two triangles with a common edge. We also check the case $n=3$ by hand. We now solve the problem by induction. It suffices to show that for any graph $G$ with $2n$ vertices and $n^2+1$ edges that we can delete some two vertices which removes at most $2n-1$ edges. For any vertex $v$, let $d_v$ denote the degree of vertex $v$. Furthermore, for any two distinct vertices $v$ and $w$, let $e_{vw}$ be $1$ if $vw$ is an edge and $0$ otherwise. If we delete $v$ and $w$, then we remove at most $d_v+d_w-e_{vw}$ edges. Pick any $\{v,w\}\subset V$ uniformly at random. Then, \[\mathcal{E}:=\mathbb{E}[d_v+d_w-e_{vw}]=\frac{4|E|}{|V|}-\frac{|E|}{\binom{|V|}{2}}.\]We now compute \[\mathcal{E}=\frac{2(n^2+1)}{n}-\frac{n^2+1}{n(2n-1)}=2n\left(1+\frac{1}{n^2}\right)\left(1-\frac{1}{2(2n-1)}\right)<2n\]for $n\ge 4$. Thus, there are some $v$ and $w$ such that we remove at most $2n-1$ edges, as desired.

We will prove the problem by induction on $n$.Base cases can be checked by hand. For $n\ge 4$, consider any graph $G$ with $2n$ vertices and $n^2+1$ edges.By Turan's theorem this graph contains a triangle $ABC$.Let $V(G)$ denote the set of vertices of $G$. For any vertex $v\in V(G)-\{A,B,C\}$ if $v$ is a neighbour of any 2 of $\{A,B,C\}$ then we will get a $K_{4}- \text{One edge}$. Otherwise,assume any vertex in $V(G)-\{A,B,C\}$ is incident with atmost 1 of $\{A,B,C\}$.Hence we get , $$\deg(A)+\deg(B)+\deg(C)\le (2n-3)+6$$+6 because each of $AB,BC,CA$ is counted twice. So by php, $$\min\{\deg(A)+\deg(B),\deg(B)+\deg(C),\deg(C)+\deg(A)\}\le \frac{2}{3}((2n-3)+6)$$So WLOG assume $$\deg(A)+\deg(B)\le \frac{4}{3}n+2\le 2n-1$$So $G'=G-\{A,B\}$ has $2n-2$ vetex and atleast $n^2+1-(2n-1)=(n-1)^2+1$.By induction hypothesis, $G'$ has a $K_{4}- \text{One edge}$. We are done $\blacksquare$

Start off with $2n$ vertices.Consider vertices $A,B$ on an edge of a triangle(exists due to Turan's theorem) such that $d_{A}+d_{B}$ is even.If $d_{A}+d_{B} \ge 2n+2$,then there exists two common neighbours and we are done. If $d_{A}+d_{B} \le 2n$,then on deleting vertices $A,B$ atmost $2n-1$ edges get deleted and we are done by induction.

We proceed with induction on $n$. Assume the statement for $k$. Let graph $G$ have $(k+1)^2+1$ edges and $2k+2$ vertices. Choose two vertices $v$ and $u$ with $vu\in E(G)$. Let $G'$ be the graph resulting from removing $v$ and $u$ from $G$. In order for there to be no two triangles sharing a common edge, the number of edges incident to $v$ or $u$ (or both) is at most $2k+2$. There are two cases to consider: Case 1. There are at most $2k+1$ such edges, $|E(G')|\geq (k+1)^2+1-(2k+1)=k^2+1$, so $G'\subset G$ contains two triangles sharing a common edge. Case 2. There are exactly $2k+2$ such edges, $|E(G')|=(k+1)^2+1-(2k+2)=k^2$. Note that in order for there to be no two triangles sharing a common edge, there is exactly one vertex in $G'$ incident to both $v$ and $u$. Call this vertex $x$. Define \begin{align*} A&=\{a\in V(G')\mid av\in E(G),au\notin E(G)\}\\ B&=\{b\in V(G')\mid av\notin E(G),au\in E(G)\} \end{align*}so $|A|+|B|=2k-1$. There are at most $|A||B|\leq k(k-1)$ edges between $A$ and $B$. No edge in $G'$ can be incident to $x$ (otherwise $G'$ contains a triangle sharing a common edge) so the among the remaining $\geq k$ edges, there must exist two adjacent edges with all endpoints in either $A$ or $B$. These edges, along with $v$ or $u$, determine two triangles sharing a common edge. Thus the statement holds for $k+1$. $\square$

Perform induction, with base cases straightforward. The idea is to actually work backwards. Assume the inductive hypothesis and for sake of contradiction that the result is not true. Claim. There exist a pair of vertices $u, v \in G$ such that deleting $u$ and $v$ removes at most $2n-1$ edges from the graph. Proof. The idea is to consider the sum $\deg u + \deg v - 1_{uv}$, where $1_{uv} = 1$ if $uv$ is an edge and $0$ otherwise. Across all $u, v$ this evaluates to $$\sum_{u, v \in G} (\deg u + \deg v) - (n^2+1) = 2(2n-1)(n^2+1),$$so over all ${2n \choose 2}$ pairs of vertices, the average value of the sum is less than $2n$, hence the result. Thus just remove these vertices and induct.