op_193_clique_free_edge_bound
A finite graph with no (r+1)-clique, where r is positive, has at most (r-1)n²/(2r) edges, expressed without division.
Statement
theorem op_193_clique_free_edge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r : ℕ) (hr : 0 < r) (hfree : G.CliqueFree (r+1)) : 2*r*G.edgeFinset.card ≤ (r-1)*(Fintype.card V)^2
- Source
- Mathlib clique-free extremal graph bound.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
Turán's theorem implies that among all graphs on |V| vertices with no (r+1)-clique, the Turán graph maximizes the number of edges. The proof introduces a Turán-maximal graph H on V, so |E(G)| ≤ |E(H)| because G is (r+1)-clique-free. Since H is Turán-maximal, it is isomorphic to the standard Turán graph T(|V|, r) and therefore has the same edge count. Multiplying by 2r and applying the known edge bound for the Turán graph yields the desired inequality 2r * |E(G)| ≤ (r - 1)|V|².
There exists a Turán-maximal graph H with parameter r on the vertex set V.
Applying exists_isTuranMaximal for r > 0 yields a graph H on V that maximizes edges among (r+1)-clique-free graphs, along with decidability of its adjacency relation (which is registered as a typeclass instance for subsequent edge counting).
uses
exists_isTuranMaximalobtain ⟨H, hd, hmax⟩ := exists_isTuranMaximal (V := V) hr letI : DecidableRel H.Adj := hdThe number of edges in G is at most the number of edges in H: |E(G)| ≤ |E(H)|.
By the definition of a Turán-maximal graph (the second projection of hmax), every (r+1)-clique-free graph on V has at most as many edges as H. Since G is (r+1)-clique-free by assumption (hfree), this inequality holds for G.
have hle : G.edgeFinset.card ≤ H.edgeFinset.card := hmax.2 hfreeThe number of edges in H equals the number of edges in the standard Turán graph T(|V|, r).
By isTuranMaximal_iff_nonempty_iso_turanGraph, a graph is Turán-maximal if and only if it is isomorphic to the Turán graph T(|V|, r). Extracting such an isomorphism and applying card_edgeFinset_eq shows that H and T(|V|, r) have the same number of edges.
uses
isTuranMaximal_iff_nonempty_iso_turanGraph,card_edgeFinset_eqhave heq : H.edgeFinset.card = (turanGraph (Fintype.card V) r).edgeFinset.card := ((isTuranMaximal_iff_nonempty_iso_turanGraph hr).mp hmax).some.card_edgeFinset_eq2r * |E(G)| ≤ (r - 1)|V|²
We chain three relations: multiplying |E(G)| ≤ |E(H)| by 2r on the left gives 2r * |E(G)| ≤ 2r * |E(H)| via Nat.mul_le_mul_left; replacing |E(H)| by the edge count of T(|V|, r) using the previously established equality preserves the value; finally, the known Turán graph edge bound mul_card_edgeFinset_turanGraph_le bounds this by (r - 1)|V|².
uses
Nat.mul_le_mul_left,mul_card_edgeFinset_turanGraph_lecalc 2*r*G.edgeFinset.card ≤ 2*r*H.edgeFinset.card := Nat.mul_le_mul_left _ hle _ = 2*r*(turanGraph (Fintype.card V) r).edgeFinset.card := by rw [heq] _ ≤ (r-1)*(Fintype.card V)^2 := mul_card_edgeFinset_turanGraph_le
exists_isTuranMaximal- For any finite vertex type V and any r > 0, there exists a graph on V that is Turán-maximal for parameter r.
isTuranMaximal_iff_nonempty_iso_turanGraph- A graph on a finite vertex set V is Turán-maximal for parameter r > 0 if and only if it is isomorphic to the Turán graph T(|V|, r).
card_edgeFinset_eq- An isomorphism between two simple graphs preserves the cardinality of their edge sets.
Nat.mul_le_mul_left- Multiplying both sides of an inequality a ≤ b on the left by k gives k * a ≤ k * b for natural numbers.
mul_card_edgeFinset_turanGraph_le- For any n and r, the Turán graph T(n, r) satisfies 2r * e(T(n, r)) ≤ (r - 1)n².
- The step introducing the decidability instance for adjacency on H (line 9) is formal bookkeeping required by Lean to define the finite edge set of H.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperatorsopen SimpleGraphtheorem op_193_clique_free_edge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (r : ℕ) (hr : 0 < r) (hfree : G.CliqueFree (r+1)) : 2*r*G.edgeFinset.card ≤ (r-1)*(Fintype.card V)^2 := by obtain ⟨H, hd, hmax⟩ := exists_isTuranMaximal (V := V) hr letI : DecidableRel H.Adj := hd have hle : G.edgeFinset.card ≤ H.edgeFinset.card := hmax.2 hfree have heq : H.edgeFinset.card = (turanGraph (Fintype.card V) r).edgeFinset.card := ((isTuranMaximal_iff_nonempty_iso_turanGraph hr).mp hmax).some.card_edgeFinset_eq calc 2*r*G.edgeFinset.card ≤ 2*r*H.edgeFinset.card := Nat.mul_le_mul_left _ hle _ = 2*r*(turanGraph (Fintype.card V) r).edgeFinset.card := by rw [heq] _ ≤ (r-1)*(Fintype.card V)^2 := mul_card_edgeFinset_turanGraph_le