Lower bound for number of triangles in simple graph.- very hard exercise 
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.
 A: 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}$$
