Triangle removal lemma

Remarks

The standard proof applies the Szemerédi regularity lemma with a small accuracy. Delete the edges inside parts, between irregular pairs, and between pairs of low density; these are at most $\varepsilon n^2$ edges. If a triangle survives, its three parts are pairwise regular and dense, and the counting lemma then gives more than $\delta n^3$ triangles. The resulting $\delta$ is very small: the proof gives $1/\delta$ of tower type in $1/\varepsilon$.

A consequence: if every edge of a graph on $n$ vertices lies in exactly one triangle, then the graph has $o(n^2)$ edges. Indeed, if it has $e$ edges, it has $e/3 \le n^2/6$ triangles, which is less than $\delta n^3$ for large $n$. The triangles are edge-disjoint, so destroying them needs $e/3$ deletions, and the lemma gives $e/3 \le \varepsilon n^2$. Applied to a graph built from a subset of $\Z/N\Z$, this gives Roth's theorem on three-term arithmetic progressions.

Going deeper

For a student

The lemma is the simplest case of the graph removal lemma. There, any fixed graph $H$ takes the place of the triangle, and $\delta n^{|V(H)|}$ copies take the place of $\delta n^3$ triangles. It is a central tool linking extremal graph theory and additive combinatorics. Its use for Roth's theorem shows how a statement about graphs can prove a statement about integers. Better bounds for $\delta$ than tower type in this generality are a well-known open question.