= Triangle removal lemma
{title2=$\#K_3<\rho N^3\Longrightarrow\text{at most }\eta N^2\text{ edge deletions}$}
For every $\eta>0$, some $\rho>0$ and $N_0$ have this property: a <graph> on $N\geq N_0$ <vertices> with fewer than $\rho N^3$ unordered <triangles in a graph> can be made <triangle-free> by deleting at most $\eta N^2$ <edges>. A <Szemerédi regularity lemma> partition deletes exceptional, intraclass, irregular and sparse-pair <edges> cheaply. A surviving <triangle in a graph> would force a positive cubic count by the <regular triangle counting lemma>.
Back to article page
