= Solution
Choose a small density threshold $d>0$, then $\varepsilon\leq\min(d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large that
$$
2\varepsilon+\frac1{2m_0}+\frac d2<\eta.
$$
Apply the regularity lemma. Delete all <edges> incident with $V_0$, all <edges> within a class $V_i$, all <edges> between <irregular pairs>, and all <edges> between <regular pairs> of density below $d$. Their total is at most
$$
\varepsilon n^2+\frac{n^2}{2k}+\varepsilon n^2+\frac d2 n^2<\eta n^2.
$$
If a <triangle in a graph>[triangle] remains, its <vertices> lie in three distinct nonexceptional classes, all whose pairs were regular with original density at least $d$. Part (c) then forces at least $(d^3/16)t^3$ <triangle in a graph>[triangles] in the original <graph>, where $t$ is the common class size. Since $k\leq M$ and $\varepsilon\leq1/4$, we have $t\geq n/(2M)$, so this is at least $d^3n^3/(128M^3)$.
Choose $c=d^3/(256M^3)$ and take $n_0$ large enough for the regularity lemma. An original <graph> with at most $cn^3$ <triangle in a graph>[triangles] cannot leave any <triangle in a graph>[triangle] after these deletions. Thus \b[deleting at most $\eta n^2$ <edges> makes the <graph> triangle-free]. This is the <triangle removal lemma>; boundedly many large regular clusters turn any surviving <triangle in a graph>[triangle] into a positive-density family of original <triangle in a graph>[triangles].
Back to article page
