connected_graph_129_independence_three_edge_bound
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
- digraph_common_predecessor_graph_129_contradictionNo digraph on 129 vertices can have outdegree at most seven while its common-predecessor graph is connected and has no independent set of…
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.
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.
classical by_contra hbad have hlow : G.edgeFinset.card ≤ 2709 := by omega
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.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lelet 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
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.
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_righthave 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
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.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lehave 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
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.
uses
SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph,Fintype.card_finhave 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
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.
uses
SimpleGraph.compl_adj,SimpleGraph.turanGraph_adjhave 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
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).
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
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.
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.
- In Mathlib's formalization of the Turán graph `turanGraph n r`, vertices are elements of `Fin n` and two vertices are adjacent if and only if their numerical indices have different remainders 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
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.
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