The triangle removal lemma
ProvedFamousTheorems.triangle_removal_lemmaThe triangle removal lemma. For every there is such that for every finite graph on vertices with fewer than triangles, one can delete fewer than edges to make triangle-free. That is, there is a triangle-free subgraph with .
The constant depends only on . The lemma (Ruzsa–Szemerédi) is a cornerstone of the regularity method. It implies Roth's theorem and the -theorem, and is a basic example of property testing.
Formalization note. Derived from Mathlib's SimpleGraph.triangle_removal, with given by the explicit SimpleGraph.triangleRemovalBound ε. G.cliqueFinset 3 is the finset of triangles, G'.CliqueFree 3 means triangle-free, and the quantification over all finite vertex types is uniform in .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem triangle_removal_lemma {ε : ℝ} (hε : 0 < ε) :
∃ δ > (0 : ℝ), ∀ (α : Type*) [DecidableEq α] [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj],
((G.cliqueFinset 3).card : ℝ) < δ * Fintype.card α ^ 3 →
∃ G' ≤ G, ∃ _ : DecidableRel G'.Adj,
((G.edgeFinset.card : ℝ) - G'.edgeFinset.card) < ε * (Fintype.card α ^ 2 : ℕ) ∧ G'.CliqueFree 3 := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.triangle_removal`. Proof here reduces to that Mathlib result.