AFTD Auto-Formalizing Theoretical Domains

ramsey_254_regular_compl_codegree_eq_codegree

theoremverified

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.

  1. 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.

    lines 7–9

      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)
  2. 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.

    lines 10–17

    uses SimpleGraph.mem_neighborSet, Set.toFinset_card

      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]
  3. 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.

    lines 18–23

    uses SimpleGraph.mem_commonNeighbors, Set.toFinset_card, Finset.card_union_add_card_inter

      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]
  4. 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}.

    lines 24–29

    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_or

      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
  5. {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.

    lines 30–44

    uses Finset.mem_singleton, Finset.mem_insert, Finset.mem_sdiff, Finset.mem_univ, Finset.mem_union, Finset.mem_filter, true_and, Finset.card_pair

      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
  6. |(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.

    lines 45–51

    uses Finset.card_sdiff_add_card_eq_card, Finset.subset_univ

      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
  7. 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|.

    lines 52–56

    uses Set.toFinset_card

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it