card_edgeFinset_ge_55_of_no_indep_six
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
- balanced_five_coloring_exists_color_class_bounds_and_propertiesFor an arbitrary finite type V with 26 elements, if c : Sym2 V → Fin 5 is a balanced edge coloring, then some color class graph has no…
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.
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.
uses
SimpleGraph.isNClique_iff,SimpleGraph.compl_adjopen 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
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.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lehave hbound : (Gᶜ).edgeFinset.card ≤ 270 := by have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := Gᶜ) (r := 5) hcf simp [hcard] at h exact h
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.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,SimpleGraph.compl_adjhave 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]
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.
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_righthave 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]
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.
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
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.
/-- 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