seidel_matrix_row_sum_eq_degree
For a finite simple graph G with decidable adjacency and any vertex i, the i-th Seidel row sum equals |V| - 1 - 2·deg(i), where deg(i) is the number of neighbours of i.
Statement
theorem seidel_matrix_row_sum_eq_degree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (i : V) : ∑ j : V, seidel_matrix G i j = (Fintype.card V : ℤ) - 1 - 2 * (Fintype.card (G.neighborSet i) : ℤ)
- Source
- step towards ramsey_b63_b64_seidel_graph_exists
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
The proof computes the i-th row sum of the Seidel matrix by decomposing each entry S_{ij} into an arithmetic combination of indicators: S_{ij} = (if j = i then 0 else 1) - 2 * (if Adj(i, j) then 1 else 0). Summing this pointwise identity over all vertices j splits the row sum into two separate sums. The first sum counts all vertices distinct from i, evaluating to |V| - 1, while the second sum counts the neighbors of i, evaluating to deg(i). Combining these results yields the row sum |V| - 1 - 2 * deg(i).
Each entry of the Seidel matrix satisfies S_{ij} = (if j = i then 0 else 1) - 2 * (if Adj(i, j) then 1 else 0).
We verify the identity pointwise by a case split on whether j = i. When j = i, the diagonal entry is 0 by definition of the Seidel matrix, and simple graphs have no self-loops (SimpleGraph.irrefl), so the formula yields 0 - 2 * 0 = 0. When j ≠ i, the entry is -1 if i and j are adjacent and 1 if they are not; the formula yields 1 - 2 * 1 = -1 and 1 - 2 * 0 = 1 respectively, matching in both cases.
uses
seidel_matrix,SimpleGraph.irrefl,Matrix.of_apply,if_falsehave hpt : ∀ j : V, seidel_matrix G i j = (if j = i then (0:ℤ) else 1) - 2 * (if G.Adj i j then (1:ℤ) else 0) := by intro j by_cases hji : j = i · subst hji simp [seidel_matrix, SimpleGraph.irrefl] · have hij : i ≠ j := fun h => hji h.symm simp only [seidel_matrix, Matrix.of_apply, hji, hij, if_false] by_cases ha : G.Adj i j <;> simp [ha]
The sum ∑_{j : V} (if j = i then 0 else 1) equals |V| - 1.
Rewriting the summand (if j = i then 0 else 1) as 1 - (if j = i then 1 else 0) allows the sum to split into ∑_{j} 1 - ∑_{j} (if j = i then 1 else 0). The first sum counts every vertex in V, yielding |V| (using Finset.sum_const and Finset.card_univ), while the second sum evaluates to 1 because the indicator is non-zero only at j = i (Finset.sum_ite_eq'). Their difference is |V| - 1.
uses
Finset.sum_congr,Finset.sum_sub_distrib,Finset.sum_ite_eq',Finset.sum_const,Finset.card_univhave hfirst : ∑ j : V, (if j = i then (0:ℤ) else 1) = (Fintype.card V : ℤ) - 1 := by have : ∑ j : V, (if j = i then (0:ℤ) else 1) = ∑ j : V, ((1:ℤ) - if j = i then 1 else 0) := by apply Finset.sum_congr rfl intro j _ split <;> simp rw [this, Finset.sum_sub_distrib] simp [Finset.sum_ite_eq', Finset.sum_const, Finset.card_univ]
The degree of vertex i equals the cardinality of the finset of vertices adjacent to i.
The cardinality of the neighbor set is identified with that of `neighborFinset i` (via Set.toFinset_card and SimpleGraph.neighborFinset_def), which is defined as filtering the universe of vertices by adjacency to i (SimpleGraph.neighborFinset_eq_filter).
uses
Set.toFinset_card,SimpleGraph.neighborFinset_def,SimpleGraph.neighborFinset_eq_filterhave hcard : (Fintype.card (G.neighborSet i) : ℤ) = ((Finset.univ.filter (fun j => G.Adj i j)).card : ℤ) := by rw [← Set.toFinset_card (G.neighborSet i), ← SimpleGraph.neighborFinset_def, SimpleGraph.neighborFinset_eq_filter]
The sum ∑_{j : V} (if Adj(i, j) then 1 else 0) equals deg(i).
Rewriting the sum over the vertex type as a sum over Finset.univ, the sum of the boolean indicator function counts the elements of the filtered finset of neighbors (Finset.sum_boole), which was just shown to equal deg(i).
uses
Finset.sum_boolehave hsecond : ∑ j : V, (if G.Adj i j then (1:ℤ) else 0) = (Fintype.card (G.neighborSet i) : ℤ) := by rw [show (∑ j : V, (if G.Adj i j then (1:ℤ) else 0)) = ∑ j ∈ (Finset.univ : Finset V), (if G.Adj i j then (1:ℤ) else 0) by simp] rw [Finset.sum_boole, hcard]
The i-th Seidel row sum equals |V| - 1 - 2 * deg(i).
Substituting the pointwise decomposition of S_{ij} into the row sum, distributing summation over subtraction, and factoring out the constant 2 transforms the sum into the difference of the two previously evaluated sums, giving (|V| - 1) - 2 * deg(i).
uses
Finset.sum_congr,Finset.sum_sub_distrib,Finset.mul_sumrw [Finset.sum_congr rfl (fun j _ => hpt j), Finset.sum_sub_distrib, ← Finset.mul_sum, hfirst, hsecond]
seidel_matrix- The Seidel adjacency matrix of a simple graph, whose (i, j) entry is 0 on the diagonal, -1 for adjacent vertices, and 1 for distinct non-adjacent vertices.
SimpleGraph.irrefl- In a simple graph, no vertex is adjacent to itself (there are no self-loops).
Matrix.of_apply- The (i, j) entry of a matrix defined by a function f equals f(i, j).
if_false- A conditional expression `if False then t else e` simplifies to `e`.
Finset.sum_congr- Two sums over equal finite sets are equal if their terms agree on every element.
Finset.sum_sub_distrib- Summation distributes over subtraction: ∑ (f(x) - g(x)) = ∑ f(x) - ∑ g(x).
Finset.sum_ite_eq'- The sum over a finite set s of an indicator function that takes value b(x) when x = a and 0 otherwise equals b(a) if a ∈ s, and 0 otherwise.
Finset.sum_const- Summing a constant value b over a finite set s yields |s| • b.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Set.toFinset_card- The cardinality of a finite set coerced to a finset equals the cardinality of its subtype.
SimpleGraph.neighborFinset_def- The neighbor finset of a vertex is defined as the finset of its neighbor set.
SimpleGraph.neighborFinset_eq_filter- The neighbor finset of a vertex v equals the finset of vertices w filtered by adjacency to v.
Finset.sum_boole- The sum of a boolean indicator (1 if p(x) else 0) over a finite set equals the cardinality of the subset of elements satisfying p.
Finset.mul_sum- Multiplication by a constant distributes over a finite sum: a * ∑ f(i) = ∑ (a * f(i)).
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.
/-- The i-th row sum of the Seidel matrix of a finite graph is |V| - 1 - 2 * deg(i). -/theorem seidel_matrix_row_sum_eq_degree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (i : V) : ∑ j : V, seidel_matrix G i j = (Fintype.card V : ℤ) - 1 - 2 * (Fintype.card (G.neighborSet i) : ℤ) := by have hpt : ∀ j : V, seidel_matrix G i j = (if j = i then (0:ℤ) else 1) - 2 * (if G.Adj i j then (1:ℤ) else 0) := by intro j by_cases hji : j = i · subst hji simp [seidel_matrix, SimpleGraph.irrefl] · have hij : i ≠ j := fun h => hji h.symm simp only [seidel_matrix, Matrix.of_apply, hji, hij, if_false] by_cases ha : G.Adj i j <;> simp [ha] have hfirst : ∑ j : V, (if j = i then (0:ℤ) else 1) = (Fintype.card V : ℤ) - 1 := by have : ∑ j : V, (if j = i then (0:ℤ) else 1) = ∑ j : V, ((1:ℤ) - if j = i then 1 else 0) := by apply Finset.sum_congr rfl intro j _ split <;> simp rw [this, Finset.sum_sub_distrib] simp [Finset.sum_ite_eq', Finset.sum_const, Finset.card_univ] have hcard : (Fintype.card (G.neighborSet i) : ℤ) = ((Finset.univ.filter (fun j => G.Adj i j)).card : ℤ) := by rw [← Set.toFinset_card (G.neighborSet i), ← SimpleGraph.neighborFinset_def, SimpleGraph.neighborFinset_eq_filter] have hsecond : ∑ j : V, (if G.Adj i j then (1:ℤ) else 0) = (Fintype.card (G.neighborSet i) : ℤ) := by rw [show (∑ j : V, (if G.Adj i j then (1:ℤ) else 0)) = ∑ j ∈ (Finset.univ : Finset V), (if G.Adj i j then (1:ℤ) else 0) by simp] rw [Finset.sum_boole, hcard] rw [Finset.sum_congr rfl (fun j _ => hpt j), Finset.sum_sub_distrib, ← Finset.mul_sum, hfirst, hsecond]