AFTD Auto-Formalizing Theoretical Domains

card_edgeFinset_ge_55_of_no_indep_six

theoremverifiedformalization

If a simple graph on 26 vertices has no independent set of size 6, then it has at least 55 edges.

Statement

theorem card_edgeFinset_ge_55_of_no_indep_six
    {V : Type*} [Fintype V] [DecidableEq V] (hcard : Fintype.card V = 26)
    (G : SimpleGraph V) [DecidableRel G.Adj] (hA : graph_has_no_indep_six G) :
    55 ≤ G.edgeFinset.card
Formalizes
scout/2610-24484-erd-h-o-s-gy-arf-as-balanced-five-colorings.md:1291
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_has_no_indep_sixA simple graph has no independent set of size 6 if every 6-element subset of vertices contains two distinct adjacent vertices.
Used by 1

Read back from the Lean

For any finite type $V$ with decidable equality having cardinality 26, and any simple graph $G$ on $V$ with decidable adjacency: if $G$ has no independent set of size 6 (i.e., graph_has_no_indep_six G), then the number of edges of $G$ (G.edgeFinset.card) is at least 55.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

An independent set in a graph G is a clique in its complement graph Gᶜ, so the condition that G has no independent set of size 6 means that Gᶜ has no 6-clique. By Turán's theorem, a graph on 26 vertices with no 6-clique has at most 270 edges. Since the edges of G and Gᶜ partition the 325 edges of the complete graph K₂₆, G must have at least 325 - 270 = 55 edges.

  1. The complement graph Gᶜ contains no clique of size 6 (it is K₆-free).

    Suppose, for contradiction, that Gᶜ contains a 6-clique t (by SimpleGraph.isNClique_iff). By the hypothesis hA (graph_has_no_indep_six), every 6-vertex set contains two adjacent vertices in G, so there exist v, w ∈ t that are adjacent in G. Since G has no self-loops, v ≠ w. But t is a clique in Gᶜ, which means v and w must be adjacent in Gᶜ. By SimpleGraph.compl_adj, adjacency in Gᶜ means v ≠ w and ¬G.Adj v w, directly contradicting that v and w are adjacent in G.

    lines 6–15

    uses SimpleGraph.isNClique_iff, SimpleGraph.compl_adj

      open Finset in
      have hcf : Gᶜ.CliqueFree 6 := by
        intro t ht
        rw [SimpleGraph.isNClique_iff] at ht
        obtain ⟨hcl, hcard6⟩ := ht
        obtain ⟨v, hv, w, hw, hadj⟩ := hA t hcard6
        have hne : v ≠ w := hadj.ne
        have hcompl : Gᶜ.Adj v w := hcl hv hw hne
        rw [SimpleGraph.compl_adj] at hcompl
        exact hcompl.2 hadj
  2. The complement graph Gᶜ has at most 270 edges.

    By Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le) applied to the K₆-free graph Gᶜ with r = 5, the number of edges in Gᶜ is bounded by the Turán number for n = 26 vertices and r = 5 parts. Since 26 = 5 * 5 + 1, evaluating the formula ((26² - 1²) * 4) / 10 + (1 choose 2) = (675 * 4) / 10 + 0 = 270 yields at most 270 edges.

    lines 16–19

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      have hbound : (Gᶜ).edgeFinset.card ≤ 270 := by
        have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := Gᶜ) (r := 5) hcf
        simp [hcard] at h
        exact h
  3. The edge set of Gᶜ is the set difference between the edges of the complete graph ⊤ and the edges of G.

    By induction on unordered pairs (Sym2.ind), every edge e is of the form s(v, w). Rewriting using the membership conditions for edge sets (SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet) and the definition of complement adjacency (SimpleGraph.compl_adj), s(v, w) is an edge of Gᶜ if and only if v ≠ w and ¬G.Adj v w, which is precisely the condition for belonging to the edge finset of the complete graph ⊤ minus that of G.

    lines 20–24

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj

      have hcompl_edge : (Gᶜ).edgeFinset = (⊤ : SimpleGraph V).edgeFinset \ G.edgeFinset := by
        ext e
        induction e using Sym2.ind with
        | _ v w =>
          simp [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj]
  4. The sum of the edge counts of Gᶜ and G is 325.

    Replacing the edges of Gᶜ with E(⊤) \ E(G), since G ≤ ⊤ (le_top and SimpleGraph.edgeFinset_subset_edgeFinset.2), the sizes satisfy |E(⊤) \ E(G)| + |E(G)| = |E(⊤)| by Finset.card_sdiff_add_card_eq_card. The complete graph ⊤ on 26 vertices has (26 choose 2) edges (SimpleGraph.card_edgeFinset_top_eq_card_choose_two), and 26 * 25 / 2 = 325 by Nat.choose_two_right.

    lines 25–30

    uses Finset.card_sdiff_add_card_eq_card, SimpleGraph.edgeFinset_subset_edgeFinset.2, le_top, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right

      have hsum : (Gᶜ).edgeFinset.card + G.edgeFinset.card = 325 := by
        rw [hcompl_edge]
        rw [Finset.card_sdiff_add_card_eq_card
          (SimpleGraph.edgeFinset_subset_edgeFinset.2 le_top)]
        rw [SimpleGraph.card_edgeFinset_top_eq_card_choose_two, hcard]
        norm_num [Nat.choose_two_right]
  5. The graph G has at least 55 edges.

    From |E(Gᶜ)| ≤ 270 and |E(Gᶜ)| + |E(G)| = 325, linear integer arithmetic (omega) immediately concludes |E(G)| ≥ 325 - 270 = 55.

    line 31

      omega
SimpleGraph.isNClique_iff
A set of vertices is an n-clique if and only if it is a clique and its cardinality is n.
SimpleGraph.compl_adj
Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
SimpleGraph.CliqueFree.card_edgeFinset_le
Turán's theorem: in a graph on n vertices without an (r + 1)-clique, the number of edges is at most ((n² - (n % r)²) * (r - 1)) / (2 * r) + (n % r choose 2).
Sym2.ind
Every unordered pair in Sym²(α) is of the form s(x, y) for some vertices x and y.
SimpleGraph.mem_edgeFinset
An unordered pair is an element of a graph's edge finset if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
Finset.card_sdiff_add_card_eq_card
If s is a subset of t, then |t \\ s| + |s| = |t|.
SimpleGraph.edgeFinset_subset_edgeFinset.2
If graph G₁ is a subgraph of G₂ (G₁ ≤ G₂), then the edge finset of G₁ is a subset of the edge finset of G₂.
le_top
In any type with an order and a top element, every element is less than or equal to ⊤.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The complete graph on a vertex set V has (card V choose 2) edges.
Nat.choose_two_right
For any natural number n, (n choose 2) = n * (n - 1) / 2.

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

/-- Any graph on 26 vertices with no independent set of size 6 has at least 55 edges. -/theorem card_edgeFinset_ge_55_of_no_indep_six    {V : Type*} [Fintype V] [DecidableEq V] (hcard : Fintype.card V = 26)    (G : SimpleGraph V) [DecidableRel G.Adj] (hA : graph_has_no_indep_six G) :    55 ≤ G.edgeFinset.card := by  open Finset in  have hcf : Gᶜ.CliqueFree 6 := by    intro t ht    rw [SimpleGraph.isNClique_iff] at ht    obtain ⟨hcl, hcard6⟩ := ht    obtain ⟨v, hv, w, hw, hadj⟩ := hA t hcard6    have hne : v ≠ w := hadj.ne    have hcompl : Gᶜ.Adj v w := hcl hv hw hne    rw [SimpleGraph.compl_adj] at hcompl    exact hcompl.2 hadj  have hbound : (Gᶜ).edgeFinset.card ≤ 270 := by    have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := Gᶜ) (r := 5) hcf    simp [hcard] at h    exact h  have hcompl_edge : (Gᶜ).edgeFinset = (⊤ : SimpleGraph V).edgeFinset \ G.edgeFinset := by    ext e    induction e using Sym2.ind with    | _ v w =>      simp [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj]  have hsum : (Gᶜ).edgeFinset.card + G.edgeFinset.card = 325 := by    rw [hcompl_edge]    rw [Finset.card_sdiff_add_card_eq_card      (SimpleGraph.edgeFinset_subset_edgeFinset.2 le_top)]    rw [SimpleGraph.card_edgeFinset_top_eq_card_choose_two, hcard]    norm_num [Nat.choose_two_right]  omega
See it in the graphDiscuss this resultChallenge it