= Solution
Let $T$ be the number of <triangles in a graph>[triangles]. Each edge $uv$ has at least
$d(u)+d(v)-n$ <common neighbours>, and summing common-neighbour counts over <edges> counts every triangle three times. Hence
$$
\begin{aligned}
3T
&\geq\sum_{uv\in E}(d(u)+d(v)-n)\\
&=\sum_vd(v)^2-ne
\geq\frac{4e^2}{n}-ne
=e\left(\frac{4e}{n}-n\right).
\end{aligned}
$$
If $e>(1+\delta)n^2/4$, this is greater than
$\delta en>\delta n^3/4$. Therefore
$$
\boxed{T>\frac{\delta}{12}n^3},
$$
so one may take $\varepsilon=\delta/12$.
Back to article page
