Let $G$ be a graph with $n$ vertices and at least $\lfloor {n^2/4}\rfloor+1$ edges, Then $G$ contains at least $\lfloor n/2\rfloor$ triangles.
This can be proven using induction by removing a single vertex. However, the following alternative proof (taken from the first paragraph here ) claims to prove the same more elegantly by removing two vertices. The end of this proof seems somewhat unjustified for me, and I'd like to know why it is true.
I understand the following: Assume there are less than $\lfloor n/2\rfloor$ triangles. We note that there is an edge $xy$ in $G$ that is not part of a triangle, and that the graph $H$ obtained by removing $x$ and $y$ from $G$ has, by induction, at least $\lfloor n/2\rfloor-1$ triangles. Now we only need to find one more triangle, and it enough to see that $N^*(x)$ (the punctured neighborhood of x) or $N^*(y)$ contain an edge. Asume to the contrary that both $N^*(x)$ and $N^*(y)$ are independent sets. Then we there are at most $\lfloor \frac{{n-2}^2}{4}\rfloor$ edges joining $N^*(x)$ to $N^*(y)$.
However, I don't see how to proceed; where is the contradiction that implies that there must indeed be an edge in $N^*(x)$ or in $N^*(y)$? Moreover, looking at a clique $K_{n-2}$ together with an additional edge $xy$ seems to be a counterexample to the proof. So is the argument really flawed? If so, can it be fixed?
Sidenote. If I knew that $H$ consists solely of vertices from $N^*(x)$ and from $N^*(y)$ then I would have known how to finish: $H$ has at least $\lfloor \frac{{n-2}^2}{4}\rfloor+1$ edges and only $\lfloor \frac{{n-2}^2}{4}\rfloor$ edges joining $N^*(x)$ to $N^*(y)$ so $N^*(y)$ or $N^*(x)$ must contain an edge.
I believe this can be solved, by proving a more general solution.
Let $G$ be a graph with $n\geq 3$ vertices and at least $\lfloor\frac{n^2}{4}\rfloor+k$ edges, for $1\leq k\leq \lfloor\frac{n-2}{6}\rfloor$. Then $G$ contains at least k$\lfloor n/2\rfloor$ triangles. The upper limit on $k$ is a bit of a fiddle, and means you may need to establish things a bit more.
But the proof is then saved, I think.
You can still find edge $(x,y)$ that's not in any triangles, since $3(k\lfloor\frac{n}{2}\rfloor-1)\leq \lfloor\frac{n^2}{4}\rfloor+1$.
Then adding in the edges from $x$ and $y$, at most one of those edges can be in $H$, since you add at least $\lfloor\frac{n-2}{2}\rfloor\geq k$ triangles per edge added to $H$.
I haven't done this rigorously, but I think you might be able to save the proof.
It's always tricky to find faults in proofs of true results, so good job on spotting this gap!!