# Triangles in a simple graph

Let $G$ be a simple (no loops, no parallel arrows) graph with $E$ edges and $V$ vertices. Then $G$ contains at least $\dfrac{E}{3V}(4E-V^2)$ triangles.

1. Let us count, first, a lower bound for the number of triangles that contain an edge $v,w$. Note that this is exactly the number of common neighbours of $late v,w$, which is at least $\deg v+\deg w-|G|$ (by inclusion exclusion on two sets). Let $\Delta$ be the number of triangles in $G$. Then $3\Delta\geqslant \sum_{w,v\; \rm edge} \deg v+\deg w- EV$.
Now the first sum is $\dfrac 1 2 \sum_{v\in V(G)}\sum_{w\in N(v)}(\deg v +\deg w)$ which equals $\dfrac 1 2 \left(\sum_v (\deg v)^ 2 + \sum_{v\in V(G)} \sum_{w\in N(v)} \deg w \right)$, and this last sum is also $\sum_v (\deg v)^ 2$. Hence $3\Delta$ is at least $\sum_v (\deg v)^ 2 -EV$. But $V \sum_v (\deg v)^ 2 \geqslant (2E)^2$: the left side counts $(v,v',w,w')$ such that $vw,vw'$ are edges of $G$, and the right side counts $(v,v',w,w')$ such that $vv',ww'$ are edges of $G$. The result follows.