AFTD Auto-Formalizing Theoretical Domains

connected_graph_129_independence_three_edge_bound

theoremverified

Every connected simple graph on 129 vertices with no independent set of size four has at least 2710 edges.

Statement

theorem connected_graph_129_independence_three_edge_bound
    (G : SimpleGraph (Fin 129)) [DecidableRel G.Adj]
    (hconn : G.Connected) (hindep : G.IndepSetFree 4) :
    2710 ≤ G.edgeFinset.card
Source
Equality-case refinement of the common-in-neighbor graph count in arXiv:2610.11517 Proposition 4.3 and DOI:10.1006/jctb.1996.0062 Claim 2, serving OP-110.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
  • Arena.Reachable.transReachability is transitive.
Used by 1

The proof, explained

The proof argues by contradiction: if the graph G on 129 vertices had at most 2709 edges, its complement H = Gᶜ would have at least 8256 - 2709 = 5547 edges. Since G has no independent set of size 4, H is K₄-free, so Turán's theorem bounds |E(H)| ≤ 5547, forcing equality and making H isomorphic to the complete tripartite Turán graph T(129, 3). Under this isomorphism, edges of G can only connect vertices within the same tripartition class (those with identical indices modulo 3). Since G is connected, all its vertices would have to belong to a single residue class modulo 3, which is impossible because vertices with different residues exist.

  1. Assume for contradiction that G has at most 2709 edges.

    We proceed by contradiction: assuming G does not have at least 2710 edges, its edge count is at most 2709 by integer arithmetic.

    lines 8–10

      classical
      by_contra hbad
      have hlow : G.edgeFinset.card ≤ 2709 := by omega
  2. The complement graph H = Gᶜ has no 4-clique and has at most 5547 edges.

    Let H be the complement graph of G. Since an independent set of size 4 in G corresponds to a 4-clique in H, H is K₄-free. Applying Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le with r = 3) on 129 vertices yields |E(H)| ≤ (129² * 2) / 6 = 5547 edges, since 129 is divisible by 3.

    lines 11–16

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      let H := Gᶜ
      have hfree : H.CliqueFree 4 := by simpa [H] using hindep
      have hupper : H.edgeFinset.card ≤ 5547 := by
        have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree
        norm_num at h
        exact h
  3. The complement graph H has exactly 5547 edges.

    The edge sets of G and H = Gᶜ are disjoint and their union is the edge set of the complete graph K₁₂₉. Thus |E(G)| + |E(H)| = (129 choose 2) = 8256. Since |E(G)| ≤ 2709 and |E(H)| ≤ 5547, the sum can only reach 8256 if |E(H)| = 5547.

    lines 17–29

    uses SimpleGraph.disjoint_edgeFinset, disjoint_compl_right, SimpleGraph.edgeFinset_sup, SimpleGraph.edgeFinset_inj.mpr, sup_compl_eq_top, Finset.card_union_of_disjoint, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right

      have hdis : Disjoint G.edgeFinset H.edgeFinset := by
        rw [SimpleGraph.disjoint_edgeFinset]
        change Disjoint G Gᶜ
        exact disjoint_compl_right
      have hunion : G.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 129)).edgeFinset := by
        rw [← SimpleGraph.edgeFinset_sup]
        change (G ⊔ Gᶜ).edgeFinset = _
        exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
      have hsum : G.edgeFinset.card + H.edgeFinset.card = 8256 := by
        rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        rw [Nat.choose_two_right]
        norm_num
      have heq : H.edgeFinset.card = 5547 := by omega
  4. H is Turán-maximal for r = 3.

    H is K₄-free and achieves the maximum possible number of edges (5547) that any K₄-free graph on 129 vertices can have by Turán's theorem, so it is Turán-maximal.

    lines 30–35

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      have hmax : H.IsTuranMaximal 3 := by
        refine ⟨hfree, ?_⟩
        intro F inst hF
        have hf := SimpleGraph.CliqueFree.card_edgeFinset_le (G := F) (r := 3) hF
        norm_num at hf
        omega
  5. H is isomorphic to the Turán graph T(129, 3).

    By the uniqueness theorem for Turán graphs, any Turán-maximal graph with r = 3 on 129 vertices is isomorphic to T(129, 3). We choose such an isomorphism e.

    lines 36–40

    uses SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph, Fintype.card_fin

      have hiso : Nonempty (H ≃g SimpleGraph.turanGraph 129 3) := by
        have h := (SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph (G := H) (r := 3) (by decide)).mp hmax
        rw [Fintype.card_fin] at h
        exact h
      obtain ⟨e⟩ := hiso
  6. Any two adjacent vertices in G have the same residue modulo 3 under e.

    If u and v are adjacent in G, they cannot be adjacent in H = Gᶜ. Under the isomorphism e, their images e(u) and e(v) cannot be adjacent in T(129, 3). Since adjacency in the Turán graph T(129, 3) means having different remainders modulo 3, non-adjacency implies that the remainders of e(u) and e(v) modulo 3 must be equal.

    lines 41–47

    uses SimpleGraph.compl_adj, SimpleGraph.turanGraph_adj

      have hsame : ∀ u v : Fin 129, G.Adj u v → (e u).val % 3 = (e v).val % 3 := by
        intro u v huv
        have hn : ¬ H.Adj u v := by simp [H, SimpleGraph.compl_adj, huv]
        have ht : ¬ (SimpleGraph.turanGraph 129 3).Adj (e u) (e v) := by
          intro ht
          exact hn (e.map_adj_iff.mp ht)
        simpa [SimpleGraph.turanGraph_adj] using ht
  7. Any two vertices connected by a path in G have the same residue modulo 3 under e.

    By induction on the length of a walk in G connecting u and v: an empty walk is the reflexive case u = v; for a non-empty walk, the first edge preserves the residue modulo 3 by the previous step, and the remaining walk does so by the induction hypothesis. Transitivity gives e(u) ≡ e(v) (mod 3).

    lines 48–53

      have hreach : ∀ u v : Fin 129, G.Reachable u v → (e u).val % 3 = (e v).val % 3 := by
        intro u v hr
        obtain ⟨p⟩ := hr
        induction p with
        | nil => rfl
        | cons h p ih => exact (hsame _ _ h).trans ih
  8. Contradiction: G cannot be connected.

    Because G is connected, every pair of vertices is connected by a walk. In particular, the vertices e⁻¹(0) and e⁻¹(1) are reachable from each other, which implies 0 ≡ 1 (mod 3). This arithmetic contradiction refutes the initial assumption.

    lines 54–56

      have hcontra := hreach (e.symm 0) (e.symm 1) (hconn _ _)
      simp only [e.apply_symm_apply] at hcontra
      norm_num at hcontra
SimpleGraph.CliqueFree.card_edgeFinset_le
A graph on n vertices with no clique of size r + 1 has at most as many edges as the Turán graph T(n, r).
SimpleGraph.disjoint_edgeFinset
Two graphs have disjoint edge sets if and only if they are disjoint as graphs (share no edges).
disjoint_compl_right
Any element in a Boolean or Heyting algebra is disjoint from its complement.
SimpleGraph.edgeFinset_sup
The edge set of the union (join) of two graphs is the union of their edge sets.
SimpleGraph.edgeFinset_inj.mpr
If two graphs are equal, their edge sets are equal.
sup_compl_eq_top
The union (join) of an element with its complement is the top element (the complete graph).
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The complete graph on a vertex set of size n has n choose 2 edges.
Nat.choose_two_right
For any natural number n, n choose 2 equals n * (n - 1) / 2.
SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph
For r > 0, a graph is Turán-maximal for cliques of size r + 1 if and only if it is isomorphic to the Turán graph T(n, r).
Fintype.card_fin
The cardinality of Fin n 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.turanGraph_adj
Two vertices in the Turán graph T(n, r) are adjacent if and only if their indices are not congruent modulo r.

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

set_option maxRecDepth 100000set_option maxHeartbeats 0theorem connected_graph_129_independence_three_edge_bound    (G : SimpleGraph (Fin 129)) [DecidableRel G.Adj]    (hconn : G.Connected) (hindep : G.IndepSetFree 4) :    2710 ≤ G.edgeFinset.card := by  classical  by_contra hbad  have hlow : G.edgeFinset.card ≤ 2709 := by omega  let H := Gᶜ  have hfree : H.CliqueFree 4 := by simpa [H] using hindep  have hupper : H.edgeFinset.card ≤ 5547 := by    have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree    norm_num at h    exact h  have hdis : Disjoint G.edgeFinset H.edgeFinset := by    rw [SimpleGraph.disjoint_edgeFinset]    change Disjoint G Gᶜ    exact disjoint_compl_right  have hunion : G.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 129)).edgeFinset := by    rw [← SimpleGraph.edgeFinset_sup]    change (G ⊔ Gᶜ).edgeFinset = _    exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top  have hsum : G.edgeFinset.card + H.edgeFinset.card = 8256 := by    rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]    rw [Nat.choose_two_right]    norm_num  have heq : H.edgeFinset.card = 5547 := by omega  have hmax : H.IsTuranMaximal 3 := by    refine ⟨hfree, ?_⟩    intro F inst hF    have hf := SimpleGraph.CliqueFree.card_edgeFinset_le (G := F) (r := 3) hF    norm_num at hf    omega  have hiso : Nonempty (H ≃g SimpleGraph.turanGraph 129 3) := by    have h := (SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph (G := H) (r := 3) (by decide)).mp hmax    rw [Fintype.card_fin] at h    exact h  obtain ⟨e⟩ := hiso  have hsame : ∀ u v : Fin 129, G.Adj u v → (e u).val % 3 = (e v).val % 3 := by    intro u v huv    have hn : ¬ H.Adj u v := by simp [H, SimpleGraph.compl_adj, huv]    have ht : ¬ (SimpleGraph.turanGraph 129 3).Adj (e u) (e v) := by      intro ht      exact hn (e.map_adj_iff.mp ht)    simpa [SimpleGraph.turanGraph_adj] using ht  have hreach : ∀ u v : Fin 129, G.Reachable u v → (e u).val % 3 = (e v).val % 3 := by    intro u v hr    obtain ⟨p⟩ := hr    induction p with    | nil => rfl    | cons h p ih => exact (hsame _ _ h).trans ih  have hcontra := hreach (e.symm 0) (e.symm 1) (hconn _ _)  simp only [e.apply_symm_apply] at hcontra  norm_num at hcontra
See it in the graphDiscuss this resultChallenge it