Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / A / 3 / d / Solution

Choose a small density threshold $d>0$, then $\epsilon \le \min (d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large thatApply 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 mostIf a 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$ triangles in the original graph, where $t$ is the common class size. Since $k\le M$ and $\epsilon \le 1/4$, we have $t\ge n/(2M)$, so this is at least $d^3{n}^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 $c{n}^3$ triangles cannot leave any triangle after these deletions. Thus 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 into a positive-density family of original triangles.