AFTD Auto-Formalizing Theoretical Domains

seidel_matrix_codegree_eq

theoremverifiedformalization

For any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in G, four times the number of common neighbors of u and v equals |V| - 4 - ∑_k S_{uk} - ∑_k S_{vk} + (S^2)_{uv}.

Statement

theorem seidel_matrix_codegree_eq {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (huv : G.Adj u v) :
    4 * (Fintype.card (G.commonNeighbors u v) : ℤ) =
      (Fintype.card V : ℤ) - 4 - (∑ k : V, seidel_matrix G u k) - (∑ k : V, seidel_matrix G v k) +
        (seidel_matrix G * seidel_matrix G) u v
Formalizes
arXiv:2610.36522 Lemma 7
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • seidel_matrixThe Seidel matrix of a simple graph G is the matrix S with zero on the diagonal, -1 for adjacent pairs of vertices, and 1 for distinct…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1
  • seidel_codegree_bounds_254For any simple graph G on 254 vertices with decidable adjacency whose Seidel matrix S has all row sums equal to 1 and (S^2)_{ij} ≤ 0 for…

Read back from the Lean

For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, and any two vertices $u, v : V$ such that $u$ and $v$ are adjacent in $G$ ($G\text{.Adj } u\ v$): $4$ times the number of common neighbors of $u$ and $v$ (as an integer) is equal to: $$|V| - 4 - \left(\sum_{k : V} S_{u, k}\right) - \left(\sum_{k : V} S_{v, k}\right) + (S^2)_{u, v}$$ where $S = \text{seidel\_matrix } G$ is the Seidel matrix of $G$, and $(S^2)_{u, v}$ is the $(u, v)$-entry of the matrix product $S * S$.

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

The proof evaluates the sum ∑_{k ∈ V} (1 - S_{uk})(1 - S_{vk}) in two different ways. Pointwise case analysis shows that each summand is 4 if k is a common neighbor of u and v, 2 if k ∈ {u, v}, and 0 otherwise, so the sum equals 4 times the number of common neighbors plus 4. Expanding the product algebraically yields |V| - ∑_k S_{uk} - ∑_k S_{vk} + (S²)_{uv} using the symmetry of the Seidel matrix. Equating the two evaluations and rearranging yields the codegree formula.

  1. The Seidel matrix of any simple graph G is symmetric: S_{ij} = S_{ji} for all vertices i and j.

    By definition, the entry S_{ij} is 0 if i = j, -1 if i and j are adjacent, and 1 otherwise. Because equality of vertices and adjacency in a simple graph are both symmetric relations, swapping i and j leaves every condition unchanged.

    line 8

    uses seidel_matrix_codegree_eq_apply, eq_comm, G.adj_comm

      simp only [seidel_matrix_codegree_eq_apply, eq_comm (a := i) (b := j), G.adj_comm i j]
  2. For every vertex k, (1 - S_{uk})(1 - S_{vk}) equals 4 if k is a common neighbor of u and v, 2 if k = u or k = v, and 0 otherwise.

    Since u and v are adjacent, u ≠ v. By the definition of the Seidel matrix, the diagonal entries are 0, adjacent pairs have entry -1, and non-adjacent pairs have entry 1. If k = u, then S_{uu} = 0 and S_{vu} = -1 (since v is adjacent to u), so (1 - 0)(1 - (-1)) = 2. Symmetrically, if k = v, the product is 2. If k is distinct from both u and v, the product is (1 - (-1))² = 4 when k is adjacent to both, and 0 when k is non-adjacent to at least one of them because at least one factor becomes 1 - 1 = 0.

    lines 16–38

    uses seidel_matrix_codegree_eq_apply, SimpleGraph.commonNeighbors, Set.mem_inter_iff, SimpleGraph.mem_neighborSet, eq_comm

      open Finset in
      have h_term (k : V) :
          (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k) =
            (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +
            (if k = u then (2 : ℤ) else 0) +
            (if k = v then (2 : ℤ) else 0) := by
        have hne : u ≠ v := huv.ne
        simp only [seidel_matrix_codegree_eq_apply, SimpleGraph.commonNeighbors, Set.mem_inter_iff,
          SimpleGraph.mem_neighborSet]
        by_cases hku : k = u
        · subst hku
          have h1 : v ≠ k := hne.symm
          have h2 : G.Adj v k := huv.symm
          simp [h1, h2, eq_comm]
        · by_cases hkv : k = v
          · subst hkv
            have h1 : u ≠ k := hne
            have h2 : G.Adj u k := huv
            simp [h1, h2, eq_comm]
          · have h1 : u ≠ k := fun h => hku h.symm
            have h2 : v ≠ k := fun h => hkv h.symm
            simp [hku, hkv, h1, h2]
            by_cases ha1 : G.Adj u k <;> by_cases ha2 : G.Adj v k <;> simp [ha1, ha2]
  3. The sum over all k ∈ V of the evaluated pointwise values equals 4 |G.commonNeighbors u v| + 4.

    The summation distributes into three separate sums: the sum of the indicator for k = u (which equals 2), the sum of the indicator for k = v (which equals 2), and the sum of 4 over all common neighbors of u and v. Factoring out 4, the remaining sum counts the common neighbors using the indicator formula for set cardinality. Adding these three contributions yields 4 |G.commonNeighbors u v| + 4.

    lines 39–62

    uses Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_congr, Set.toFinset_card, Finset.sum_boole, Finset.univ, congrArg

      have h_sum_rhs :
          (∑ k : V, ((if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +
            (if k = u then (2 : ℤ) else 0) + (if k = v then (2 : ℤ) else 0))) =
          4 * (Fintype.card (G.commonNeighbors u v) : ℤ) + 4 := by
        simp only [Finset.sum_add_distrib]
        have hu : (∑ k : V, (if k = u then (2 : ℤ) else 0)) = 2 := by simp
        have hv : (∑ k : V, (if k = v then (2 : ℤ) else 0)) = 2 := by simp
        have hc : (∑ k : V, (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0)) =
            4 * (Fintype.card (G.commonNeighbors u v) : ℤ) := by
          have h : (∑ k : V, (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0)) =
              4 * ∑ k : V, (if k ∈ G.commonNeighbors u v then (1 : ℤ) else 0) := by
            rw [Finset.mul_sum]
            apply Finset.sum_congr rfl
            intro k _
            split_ifs <;> ring
          rw [h]
          congr 1
          rw [← Set.toFinset_card]
          rw [Finset.sum_boole (· ∈ G.commonNeighbors u v) Finset.univ]
          apply congrArg
          apply congrArg
          ext x
          simp
        linarith
  4. The sum ∑_{k ∈ V} (1 - S_{uk})(1 - S_{vk}) expands algebraically to |V| - ∑_k S_{uk} - ∑_k S_{vk} + (S²)_{uv}.

    Expanding each term algebraically gives (1 - S_{uk})(1 - S_{vk}) = 1 - S_{uk} - S_{vk} + S_{uk} S_{vk}. Distributing the sum over V, the constant 1 sums to |V|. By the symmetry of the Seidel matrix, S_{vk} = S_{kv}, so the sum of the products S_{uk} S_{vk} equals ∑_k S_{uk} S_{kv}, which is precisely the (u, v)-entry of the matrix product S * S.

    lines 63–80

    uses Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_const, nsmul_eq_mul, mul_one, Finset.card_univ, Matrix.mul_apply, Finset.sum_congr, seidel_matrix_codegree_eq_symm

      have h_sum_lhs :
          (∑ k : V, (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k)) =
          (Fintype.card V : ℤ) - (∑ k : V, seidel_matrix G u k) - (∑ k : V, seidel_matrix G v k) +
            (seidel_matrix G * seidel_matrix G) u v := by
        have h_alg (k : V) :
            (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k) =
            1 - seidel_matrix G u k - seidel_matrix G v k +
              seidel_matrix G u k * seidel_matrix G v k := by ring
        simp_rw [h_alg]
        simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_const,
          nsmul_eq_mul, mul_one, Finset.card_univ]
        have h_mul : (∑ k : V, seidel_matrix G u k * seidel_matrix G v k) =
            (seidel_matrix G * seidel_matrix G) u v := by
          rw [Matrix.mul_apply]
          apply Finset.sum_congr rfl
          intro k _
          rw [seidel_matrix_codegree_eq_symm G v k]
        rw [h_mul]
  5. Four times the number of common neighbors of u and v equals |V| - 4 - ∑_k S_{uk} - ∑_k S_{vk} + (S²)_{uv}.

    Since the pointwise identity holds for every k, summing it over all k shows that the algebraic expansion of the sum equals the combinatorial sum. Equating |V| - ∑_k S_{uk} - ∑_k S_{vk} + (S²)_{uv} with 4 |G.commonNeighbors u v| + 4 and isolating 4 |G.commonNeighbors u v| via linear arithmetic completes the proof.

    lines 81–88

    uses Finset.sum_congr

      have h_sum_eq :
          (∑ k : V, (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k)) =
          ∑ k : V, ((if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +
            (if k = u then (2 : ℤ) else 0) + (if k = v then (2 : ℤ) else 0)) := by
        apply Finset.sum_congr rfl
        intro k _
        exact h_term k
      linarith
G.adj_comm
Adjacency in a simple graph is symmetric: vertices i and j are adjacent if and only if j and i are adjacent.
seidel_matrix_codegree_eq_apply
The entry S_{ij} of the Seidel matrix of G is 0 if i = j, -1 if i and j are adjacent, and 1 otherwise.
SimpleGraph.commonNeighbors
The set of common neighbors of two vertices u and v, defined as the intersection of their neighbor sets.
Set.mem_inter_iff
An element belongs to the intersection of two sets if and only if it belongs to both sets.
SimpleGraph.mem_neighborSet
A vertex w is in the neighbor set of v if and only if v and w are adjacent in G.
eq_comm
Symmetry of equality: a = b is equivalent to b = a.
Finset.sum_add_distrib
A finite sum of sums distributes as the sum of the finite sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.mul_sum
Distributivity of multiplication over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Set.toFinset_card
The cardinality of the finset corresponding to a finite set equals the cardinality of the subtype.
Finset.sum_boole
Summing an indicator function over a finite set equals the cardinality of the subset of elements satisfying the predicate.
Finset.univ
The finite set of all elements of a finite type.
congrArg
Equal arguments to a function yield equal values: if a₁ = a₂ then f a₁ = f a₂.
Finset.sum_sub_distrib
A finite sum of differences distributes as the difference of finite sums: ∑ x ∈ s, (f x - g x) = ∑ x ∈ s, f x - ∑ x ∈ s, g x.
Finset.sum_const
The sum of a constant value b over a finite set s equals the cardinality of s multiplied by b.
nsmul_eq_mul
Multiplication by a natural number n via scalar action equals multiplication by the coercion of n.
mul_one
Multiplying an element by 1 on the right leaves it unchanged.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Matrix.mul_apply
The (i, k)-entry of the matrix product M * N is given by the sum ∑ j, M i j * N j k.
seidel_matrix_codegree_eq_symm
The Seidel matrix of a simple graph is symmetric: S_{ij} = S_{ji}.

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

theorem seidel_matrix_codegree_eq_apply {V : Type*} [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (i j : V) :    seidel_matrix G i j = if i = j then 0 else if G.Adj i j then -1 else 1 := rfltheorem seidel_matrix_codegree_eq_symm {V : Type*} [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (i j : V) :    seidel_matrix G i j = seidel_matrix G j i := by  simp only [seidel_matrix_codegree_eq_apply, eq_comm (a := i) (b := j), G.adj_comm i j]/-- Codegree formula for adjacent vertices in terms of the Seidel matrix. -/theorem seidel_matrix_codegree_eq {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (huv : G.Adj u v) :    4 * (Fintype.card (G.commonNeighbors u v) : ℤ) =      (Fintype.card V : ℤ) - 4 - (∑ k : V, seidel_matrix G u k) - (∑ k : V, seidel_matrix G v k) +        (seidel_matrix G * seidel_matrix G) u v := by  open Finset in  have h_term (k : V) :      (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k) =        (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +        (if k = u then (2 : ℤ) else 0) +        (if k = v then (2 : ℤ) else 0) := by    have hne : u ≠ v := huv.ne    simp only [seidel_matrix_codegree_eq_apply, SimpleGraph.commonNeighbors, Set.mem_inter_iff,      SimpleGraph.mem_neighborSet]    by_cases hku : k = u    · subst hku      have h1 : v ≠ k := hne.symm      have h2 : G.Adj v k := huv.symm      simp [h1, h2, eq_comm]    · by_cases hkv : k = v      · subst hkv        have h1 : u ≠ k := hne        have h2 : G.Adj u k := huv        simp [h1, h2, eq_comm]      · have h1 : u ≠ k := fun h => hku h.symm        have h2 : v ≠ k := fun h => hkv h.symm        simp [hku, hkv, h1, h2]        by_cases ha1 : G.Adj u k <;> by_cases ha2 : G.Adj v k <;> simp [ha1, ha2]  have h_sum_rhs :      (∑ k : V, ((if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +        (if k = u then (2 : ℤ) else 0) + (if k = v then (2 : ℤ) else 0))) =      4 * (Fintype.card (G.commonNeighbors u v) : ℤ) + 4 := by    simp only [Finset.sum_add_distrib]    have hu : (∑ k : V, (if k = u then (2 : ℤ) else 0)) = 2 := by simp    have hv : (∑ k : V, (if k = v then (2 : ℤ) else 0)) = 2 := by simp    have hc : (∑ k : V, (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0)) =        4 * (Fintype.card (G.commonNeighbors u v) : ℤ) := by      have h : (∑ k : V, (if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0)) =          4 * ∑ k : V, (if k ∈ G.commonNeighbors u v then (1 : ℤ) else 0) := by        rw [Finset.mul_sum]        apply Finset.sum_congr rfl        intro k _        split_ifs <;> ring      rw [h]      congr 1      rw [← Set.toFinset_card]      rw [Finset.sum_boole (· ∈ G.commonNeighbors u v) Finset.univ]      apply congrArg      apply congrArg      ext x      simp    linarith  have h_sum_lhs :      (∑ k : V, (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k)) =      (Fintype.card V : ℤ) - (∑ k : V, seidel_matrix G u k) - (∑ k : V, seidel_matrix G v k) +        (seidel_matrix G * seidel_matrix G) u v := by    have h_alg (k : V) :        (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k) =        1 - seidel_matrix G u k - seidel_matrix G v k +          seidel_matrix G u k * seidel_matrix G v k := by ring    simp_rw [h_alg]    simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_const,      nsmul_eq_mul, mul_one, Finset.card_univ]    have h_mul : (∑ k : V, seidel_matrix G u k * seidel_matrix G v k) =        (seidel_matrix G * seidel_matrix G) u v := by      rw [Matrix.mul_apply]      apply Finset.sum_congr rfl      intro k _      rw [seidel_matrix_codegree_eq_symm G v k]    rw [h_mul]  have h_sum_eq :      (∑ k : V, (1 - seidel_matrix G u k) * (1 - seidel_matrix G v k)) =      ∑ k : V, ((if k ∈ G.commonNeighbors u v then (4 : ℤ) else 0) +        (if k = u then (2 : ℤ) else 0) + (if k = v then (2 : ℤ) else 0)) := by    apply Finset.sum_congr rfl    intro k _    exact h_term k  linarith
See it in the graphDiscuss this resultChallenge it