AFTD Auto-Formalizing Theoretical Domains

op_193_clique_free_edge_bound

theoremverified

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|².

  1. 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).

    lines 8–9

    uses exists_isTuranMaximal

      obtain ⟨H, hd, hmax⟩ := exists_isTuranMaximal (V := V) hr
      letI : DecidableRel H.Adj := hd
  2. The 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.

    line 10

      have hle : G.edgeFinset.card ≤ H.edgeFinset.card := hmax.2 hfree
  3. The 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.

    lines 11–12

    uses isTuranMaximal_iff_nonempty_iso_turanGraph, card_edgeFinset_eq

      have heq : H.edgeFinset.card = (turanGraph (Fintype.card V) r).edgeFinset.card :=
        ((isTuranMaximal_iff_nonempty_iso_turanGraph hr).mp hmax).some.card_edgeFinset_eq
  4. 2r * |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|².

    lines 13–16

    uses Nat.mul_le_mul_left, mul_card_edgeFinset_turanGraph_le

      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
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².

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

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
See it in the graphDiscuss this resultChallenge it