Lower bound for number of triangles in simple graph.- very hard exercise

Question

Let $G=(V,E)$ be a graph on $n$ vertices. Let $t(G)$ be a number of triangles in it.

Prove that $t(G) \ge |E|\frac{4|E|-n^2}{3n}$

My approach

|E| stands for number of edges in graph. For $t(G)=0$ I obtained it easily from Mantel's Theorem. I dont know how to do it for any $t(G)$. I tried to prove it generally in many ways:

• by induction on number of triangles; I was trying to "remove" chosen triangle, but removing one triangle can destroy a lot of triangles as it edges can be edges of many triangles.
• by induction on number of vertices;
• by induction on number of edges; But removing one edge can destroy any number of triangles in general...
• by looking at complementary graph;
• by looking at dual graph.

Nothing works.

What I know: - If G is not connected, then number of triangles is a sum of number of triangles in every connected part so we can assume that G is connected because if not, the result can be obtained by induction on number of vertices easy.

Any hints? Thanks in advance for help.

Answer 1

I think this is a hard exercise if you don't know the trick. I'll show a proof of Mantel's Theorem which uses the same idea, as a hint.

Hint: Consider the following approach to prove Mantel's Theorem.
Let $G$ be a triangle-free graph on $n$ vertices. If $xy$ is an edge then $x$ and $y$ have no common neighbour, otherwise they would form a triangle. Hence $d(x)+d(y)\leq n$.
By summing the previous inequality over the edges, we get $$\sum_{xy\in E}(d(x)+d(y))\leq n\cdot|E|$$
Note that for each vertex $v$ the term $d(v)$ is counted exactly $d(v)$ times in LHS, once for every edge incident to $v$. Thus $$\sum_{v\in G}d(v)^2=\sum_{xy\in E}(d(x)+d(y))\leq n\cdot|E|$$ We also know that $$\sqrt{\frac{\sum_{v\in G}d(v)^2}{n}}\geq\frac{\sum_{v\in G}d(v)}{n}$$ The last inequality follows from the fact that the quadratic mean of a set of non-negative numbers is always grater or equal to the arithmetic mean. You could also prove it using the Cauchy-Shwartz inequality if you are familiar with it.
Now, by the handshaking lemma $$\sum_{v\in G}d(v)=2\cdot|E|$$ Hence $$\frac{4\cdot|E|^2}{n}=\frac{(\sum_{v\in G}d(v))^2}{n}\leq\sum_{v\in G}d(v)^2=\sum_{xy}(d(x)+d(y))\leq n\cdot|E|$$ $$\implies\frac{4\cdot|E|^2}{n}\leq n\cdot|E|$$ $$\implies|E|\leq\frac{n^2}{4}$$

---

---

---

Proof of the exercise: Let $G$ be a graph on $n$ vertices. For every edge $xy\in E$ denote the number of triangles which contain $x$ and $y$ as $t_{xy}$; in particular, $t_{xy}$ is the number of common neighbours of $x$ and $y$. Thus $d(x)+d(y)\leq n+t_{xy}$; by summing this inequality over the edges: $$\sum_{xy\in E}(d(x)+d(y))\leq n\cdot|E|+\sum_{xy\in E}t_{xy}$$ Note that each triangle in $G$ is counted exactly three times in the second terms of RHS; for example, if $xyz$ is a triangle then it is counted in $t_{xy},t_{yz},t_{zx}$. Thus $$\sum_{xy\in E(G)}(d(x)+d(y))\leq n\cdot|E|+3\cdot t(G)$$ By proceeding exaclty as before, we get that $$\frac{4\cdot|E|^2}{n}\leq n\cdot|E|+3\cdot t(G)$$ $$\implies t(G)\geq \frac{1}{3}\left(\frac{4\cdot|E|^2}{n}-n\cdot|E|\right)$$ $$\implies t(G)=|E|\cdot\frac{4|E|-n^2}{3n}$$