AFTD Auto-Formalizing Theoretical Domains

seidel_matrix_row_sum_eq_degree

theoremverified

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

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

    lines 6–14

    uses seidel_matrix, SimpleGraph.irrefl, Matrix.of_apply, if_false

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

    lines 15–22

    uses Finset.sum_congr, Finset.sum_sub_distrib, Finset.sum_ite_eq', Finset.sum_const, Finset.card_univ

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

    lines 23–25

    uses Set.toFinset_card, SimpleGraph.neighborFinset_def, SimpleGraph.neighborFinset_eq_filter

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

    lines 26–29

    uses Finset.sum_boole

      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]
  5. 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).

    line 30

    uses Finset.sum_congr, Finset.sum_sub_distrib, Finset.mul_sum

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

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