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.

  • $\begingroup$ This seems not to be true for $n=2$ $\endgroup$ – Dr Xorile Nov 14 '16 at 19:05
  • $\begingroup$ Still not true for $n=2$ $\endgroup$ – Dr Xorile Nov 14 '16 at 19:07
  • $\begingroup$ 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). $\endgroup$ – Emolga Nov 14 '16 at 19:21
  • $\begingroup$ I don't think you have 1 triangle in a graph of size 2. $\endgroup$ – Dr Xorile Nov 14 '16 at 19:30
  • $\begingroup$ 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? $\endgroup$ – 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!!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.