seidel_matrix_codegree_eq
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
seidel_matrix_codegree_eq_apply,eq_comm,G.adj_commsimp only [seidel_matrix_codegree_eq_apply, eq_comm (a := i) (b := j), G.adj_comm i j]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.
uses
seidel_matrix_codegree_eq_apply,SimpleGraph.commonNeighbors,Set.mem_inter_iff,SimpleGraph.mem_neighborSet,eq_commopen 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]
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.
uses
Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_congr,Set.toFinset_card,Finset.sum_boole,Finset.univ,congrArghave 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
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.
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_symmhave 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]
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.
uses
Finset.sum_congrhave 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
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.
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