The Andrásfai–Erdős–Sós theorem
ProvedFamousTheorems.andrasfai_erdos_sos_theoremThe Andrásfai–Erdős–Sós theorem. Let and let be a -free graph on vertices. If
where is the minimum degree, then is -colourable.
For this says that a triangle-free graph with minimum degree greater than is bipartite. The theorem is a stability result for Turán's theorem: -free graphs with large minimum degree have the structure of the Turán graph. The bound is sharp.
Formalization note. Mathlib's SimpleGraph.colorable_of_cliqueFree_lt_minDegree. The bound is written with natural-number division, , which for the integer is equivalent to the strict real inequality. G.CliqueFree (r + 1) says that has no -clique.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem andrasfai_erdos_sos_theorem {α : Type*} [Fintype α] {G : SimpleGraph α} [DecidableRel G.Adj] {r : ℕ} (hG : G.CliqueFree (r + 1))
(hd : (3 * r - 4) * Fintype.card α / (3 * r - 1) < G.minDegree) : G.Colorable r := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.colorable_of_cliqueFree_lt_minDegree`. Proof here reduces to that Mathlib result.