# Fixing a proof on triangles in graphs

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.

• This seems not to be true for $n=2$ – Dr Xorile Nov 14 '16 at 19:05
• Still not true for $n=2$ – Dr Xorile Nov 14 '16 at 19:07
• Can you please elaborate? If we have two vertices and two edges we definitely have a triangle in the sense of multigraphs. (And if we only care about simple graphs then it is vacuously true). – Emolga Nov 14 '16 at 19:21
• I don't think you have 1 triangle in a graph of size 2. – Dr Xorile Nov 14 '16 at 19:30
• The proof is correct. $K_{n-2}$ would not fit with the assumption of less than $\lfloor n/2\rfloor$ triangles. Which edge are you concerned about? $xy$, or the one in the neighbourhood? – Dr Xorile Nov 14 '16 at 19:32

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!!