ramsey_254_regular_compl_codegree_eq_codegree
In a 126-regular simple graph G on 254 vertices, a pair of distinct non-adjacent vertices u and v has exactly as many common neighbours in the complement Gᶜ as in G.
Statement
theorem ramsey_254_regular_compl_codegree_eq_codegree
(G : SimpleGraph (Fin 254)) [DecidableRel G.Adj]
(hreg : ∀ i : Fin 254, Fintype.card (G.neighborSet i) = 126)
(u v : Fin 254) (hne : u ≠ v) (hna : ¬ G.Adj u v) :
Fintype.card (Gᶜ.commonNeighbors u v) = Fintype.card (G.commonNeighbors u v)- Source
- step towards ramsey_b63_b64_seidel_graph_exists
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
Let A and B be the neighbourhoods of u and v in G, each of size 126 by regularity. By inclusion-exclusion, |A ∪ B| + |A ∩ B| = 252, where A ∩ B is the set of common neighbours in G. Because u and v are non-adjacent and G has no self-loops, neither u nor v belongs to A ∪ B, so the common neighbours in the complement Gᶜ are precisely (V \ (A ∪ B)) \ {u, v}. Since the total number of vertices is 254, the complement codegree is (254 - |A ∪ B|) - 2 = 252 - |A ∪ B| = |A ∩ B|, showing that the two codegrees are equal.
Let A and B be the neighbour sets of u and v in G as finsets.
We enable classical logic and define A and B to be the finite sets of vertices adjacent in G to u and to v, respectively.
classical let A : Finset (Fin 254) := Finset.univ.filter (fun w => G.Adj u w) let B : Finset (Fin 254) := Finset.univ.filter (fun w => G.Adj v w)
Both A and B have cardinality 126.
The finsets A and B coincide with the graph neighbourhoods of u and v. By the 126-regularity assumption, both sets have cardinality 126.
uses
SimpleGraph.mem_neighborSet,Set.toFinset_cardhave hA : A.card = 126 := by have h : A = (G.neighborSet u).toFinset := by ext w; simp [A, SimpleGraph.mem_neighborSet] rw [h, Set.toFinset_card, hreg u] have hB : B.card = 126 := by have h : B = (G.neighborSet v).toFinset := by ext w; simp [B, SimpleGraph.mem_neighborSet] rw [h, Set.toFinset_card, hreg v]
The intersection A ∩ B is the set of common neighbours in G, and |A ∪ B| + |A ∩ B| = 252.
A vertex is in A ∩ B if and only if it is adjacent to both u and v, which defines the common neighbours in G. By the principle of inclusion-exclusion for finite sets, |A ∪ B| + |A ∩ B| = |A| + |B| = 126 + 126 = 252.
uses
SimpleGraph.mem_commonNeighbors,Set.toFinset_card,Finset.card_union_add_card_interhave hAB : A ∩ B = (G.commonNeighbors u v).toFinset := by ext w; simp [A, B, SimpleGraph.mem_commonNeighbors] have hABint : (A ∩ B).card = Fintype.card (G.commonNeighbors u v) := by rw [hAB, Set.toFinset_card] have hunion : (A ∪ B).card + (A ∩ B).card = 252 := by rw [Finset.card_union_add_card_inter, hA, hB]
The common neighbours of u and v in Gᶜ form the set (V \ (A ∪ B)) \ {u, v}.
A vertex w is adjacent to both u and v in Gᶜ if and only if w ≠ u, w ≠ v, and w is adjacent to neither u nor v in G. Unfolding set operations and simplifying via propositional equivalence, this means w lies in V \ (A ∪ B) and w ∉ {u, v}.
uses
Set.mem_toFinset,SimpleGraph.mem_commonNeighbors,SimpleGraph.compl_adj,Finset.mem_sdiff,Finset.mem_univ,Finset.mem_union,Finset.mem_filter,Finset.mem_insert,Finset.mem_singleton,true_and,not_orhave hcomp : (Gᶜ.commonNeighbors u v).toFinset = (Finset.univ \ (A ∪ B)) \ {u, v} := by ext w simp only [A, B, Set.mem_toFinset, SimpleGraph.mem_commonNeighbors, SimpleGraph.compl_adj, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton, true_and, not_or] tauto
{u, v} is a 2-element subset of V \ (A ∪ B).
Because simple graphs have no self-loops and u is not adjacent to v, neither u nor v can belong to the neighbourhood of u or v. Hence {u, v} ⊆ V \ (A ∪ B). Since u ≠ v, this subset has cardinality 2.
uses
Finset.mem_singleton,Finset.mem_insert,Finset.mem_sdiff,Finset.mem_univ,Finset.mem_union,Finset.mem_filter,true_and,Finset.card_pairhave hsub : ({u, v} : Finset (Fin 254)) ⊆ Finset.univ \ (A ∪ B) := by show ({u, v} : Finset (Fin 254)) ⊆ Finset.univ \ (Finset.univ.filter (fun w => G.Adj u w) ∪ Finset.univ.filter (fun w => G.Adj v w)) intro w hw simp only [Finset.mem_singleton, Finset.mem_insert] at hw rcases hw with rfl | rfl · simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, true_and] rintro (h | h) · exact G.irrefl h · exact hna h.symm · simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, true_and] rintro (h | h) · exact hna h · exact G.irrefl h have hcard_uv : ({u, v} : Finset (Fin 254)).card = 2 := Finset.card_pair hne
|(V \ (A ∪ B)) \ {u, v}| + 2 = |V \ (A ∪ B)| and |V \ (A ∪ B)| + |A ∪ B| = 254.
Since {u, v} is a 2-element subset of V \ (A ∪ B), subtracting it decreases the cardinality by 2. Furthermore, since A ∪ B is a subset of the 254-element vertex set V, the size of its complement plus |A ∪ B| is 254.
uses
Finset.card_sdiff_add_card_eq_card,Finset.subset_univhave hdiff : ((Finset.univ \ (A ∪ B)) \ {u, v}).card + 2 = (Finset.univ \ (A ∪ B)).card := by have h := Finset.card_sdiff_add_card_eq_card hsub rw [hcard_uv] at h exact h have hcompl : (Finset.univ \ (A ∪ B)).card + (A ∪ B).card = 254 := by have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ (A ∪ B)) simpa using this
The number of common neighbours of u and v in Gᶜ equals the number in G.
The codegrees in Gᶜ and G are |(V \ (A ∪ B)) \ {u, v}| and |A ∩ B|, respectively. From the system of equations |(V \ (A ∪ B)) \ {u, v}| + 2 = |V \ (A ∪ B)|, |V \ (A ∪ B)| + |A ∪ B| = 254, and |A ∪ B| + |A ∩ B| = 252, linear integer arithmetic establishes that both quantities equal 252 - |A ∪ B|.
uses
Set.toFinset_cardhave hL : Fintype.card (Gᶜ.commonNeighbors u v) = ((Finset.univ \ (A ∪ B)) \ {u, v}).card := by rw [← Set.toFinset_card, hcomp] have hR : Fintype.card (G.commonNeighbors u v) = (A ∩ B).card := hABint.symm rw [hL, hR] omega
Finset.card_union_add_card_inter- For any two finite sets s and t, the sum of the cardinalities of their union and intersection equals the sum of their individual cardinalities: |s ∪ t| + |s ∩ t| = |s| + |t|.
Finset.card_pair- The cardinality of a two-element set {a, b} with a ≠ b is 2.
Finset.card_sdiff_add_card_eq_card- If s ⊆ t, then |t \ s| + |s| = |t|.
Finset.subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
SimpleGraph.mem_neighborSet- A vertex w belongs to the neighbour set of v in a graph G if and only if v and w are adjacent in G.
SimpleGraph.mem_commonNeighbors- A vertex belongs to the set of common neighbours of u and v in G if and only if it is adjacent to both u and v.
SimpleGraph.compl_adj- Two vertices v and w are adjacent in the complement graph Gᶜ if and only if v ≠ w and they are not adjacent in G.
Set.toFinset_card- The cardinality of the finset corresponding to a finite set s equals the fintype cardinality of s.
Set.mem_toFinset- An element belongs to the finset representation of a set s if and only if it belongs to s.
Finset.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_filter- An element belongs to the sub-finset filtered by predicate p if and only if it belongs to s and satisfies p.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
true_and- The conjunction True ∧ p is equivalent to p.
not_or- De Morgan's law: ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
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.
/-- For a 126-regular graph on 254 vertices, non-adjacent pairs have equal codegree in G and in Gᶜ. -/theorem ramsey_254_regular_compl_codegree_eq_codegree (G : SimpleGraph (Fin 254)) [DecidableRel G.Adj] (hreg : ∀ i : Fin 254, Fintype.card (G.neighborSet i) = 126) (u v : Fin 254) (hne : u ≠ v) (hna : ¬ G.Adj u v) : Fintype.card (Gᶜ.commonNeighbors u v) = Fintype.card (G.commonNeighbors u v) := by classical let A : Finset (Fin 254) := Finset.univ.filter (fun w => G.Adj u w) let B : Finset (Fin 254) := Finset.univ.filter (fun w => G.Adj v w) have hA : A.card = 126 := by have h : A = (G.neighborSet u).toFinset := by ext w; simp [A, SimpleGraph.mem_neighborSet] rw [h, Set.toFinset_card, hreg u] have hB : B.card = 126 := by have h : B = (G.neighborSet v).toFinset := by ext w; simp [B, SimpleGraph.mem_neighborSet] rw [h, Set.toFinset_card, hreg v] have hAB : A ∩ B = (G.commonNeighbors u v).toFinset := by ext w; simp [A, B, SimpleGraph.mem_commonNeighbors] have hABint : (A ∩ B).card = Fintype.card (G.commonNeighbors u v) := by rw [hAB, Set.toFinset_card] have hunion : (A ∪ B).card + (A ∩ B).card = 252 := by rw [Finset.card_union_add_card_inter, hA, hB] have hcomp : (Gᶜ.commonNeighbors u v).toFinset = (Finset.univ \ (A ∪ B)) \ {u, v} := by ext w simp only [A, B, Set.mem_toFinset, SimpleGraph.mem_commonNeighbors, SimpleGraph.compl_adj, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton, true_and, not_or] tauto have hsub : ({u, v} : Finset (Fin 254)) ⊆ Finset.univ \ (A ∪ B) := by show ({u, v} : Finset (Fin 254)) ⊆ Finset.univ \ (Finset.univ.filter (fun w => G.Adj u w) ∪ Finset.univ.filter (fun w => G.Adj v w)) intro w hw simp only [Finset.mem_singleton, Finset.mem_insert] at hw rcases hw with rfl | rfl · simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, true_and] rintro (h | h) · exact G.irrefl h · exact hna h.symm · simp only [Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, true_and] rintro (h | h) · exact hna h · exact G.irrefl h have hcard_uv : ({u, v} : Finset (Fin 254)).card = 2 := Finset.card_pair hne have hdiff : ((Finset.univ \ (A ∪ B)) \ {u, v}).card + 2 = (Finset.univ \ (A ∪ B)).card := by have h := Finset.card_sdiff_add_card_eq_card hsub rw [hcard_uv] at h exact h have hcompl : (Finset.univ \ (A ∪ B)).card + (A ∪ B).card = 254 := by have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ (A ∪ B)) simpa using this have hL : Fintype.card (Gᶜ.commonNeighbors u v) = ((Finset.univ \ (A ∪ B)) \ {u, v}).card := by rw [← Set.toFinset_card, hcomp] have hR : Fintype.card (G.commonNeighbors u v) = (A ∩ B).card := hABint.symm rw [hL, hR] omega