The Erdős–Stone theorem (minimum-degree form)
ProvedFamousTheorems.erdos_stone_min_degreeThe Erdős–Stone theorem (minimum-degree form). For every and all the following holds for all sufficiently large . Every graph on vertices with minimum degree
contains the complete -partite graph with parts of size .
The Erdős–Stone theorem, often called the fundamental theorem of extremal graph theory, extends Turán's theorem: slightly more edges than the Turán graph forces not only a clique but a large complete multipartite graph. With Simonovits's corollary, it determines the asymptotic Turán number of every nonbipartite graph.
Formalization note. Mathlib's SimpleGraph.eventually_completeEquipartiteGraph_isContained_of_minDegree. Graphs on vertices are SimpleGraph (Fin n), "for all sufficiently large " is ∀ᶠ n in Filter.atTop, and IsContained is subgraph containment up to isomorphism.
import Mathlib
namespace FamousTheorems
theorem erdos_stone_min_degree {ε : ℝ} (hε : 0 < ε) (r t : ℕ) :
∀ᶠ n : ℕ in Filter.atTop, ∀ {G : SimpleGraph (Fin n)} [DecidableRel G.Adj],
(G.minDegree : ℝ) ≥ (1 - 1 / r + ε) * n → (SimpleGraph.completeEquipartiteGraph (r + 1) t).IsContained G := by sorry
end FamousTheorems