AFTD Auto-Formalizing Theoretical Domains

seidel_matrix_compl_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 the complement Gᶜ, four times the number of common neighbors of u and v in Gᶜ equals |V| - 4 + ∑_k S_{uk} + ∑_k S_{vk} + (S^2)_{uv}.

Statement

theorem seidel_matrix_compl_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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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 vertices $u, v \in V$ such that $u$ and $v$ are adjacent in the complement graph $G^c$, 4 times the number of common neighbors of $u$ and $v$ in $G^c$ (as an integer) is equal to: $|V| - 4 + \sum_{k : V} S_{u, k} + \sum_{k : V} S_{v, k} + (S^2)_{u, v}$, where $S$ is the Seidel adjacency matrix of $G$ (with entries in $\mathbb{Z}$), and all operations are in $\mathbb{Z}$.

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 relates the Seidel matrix S of G to an auxiliary function g(x, y), defined as -1 for adjacent vertices and +1 otherwise, which satisfies S_{xy} = g(x, y) - [x = y]. Summing the pointwise algebraic identity g(u, k) + g(v, k) + g(u, k) g(v, k) = 4 · [¬ u ~ k ∧ ¬ v ~ k] - 1 over all vertices k connects the row sums and the matrix product entry (S²)_{uv} to four times the number of vertices adjacent to neither u nor v. Because u and v are adjacent in the complement graph Gᶜ, they are non-adjacent in G, so the set of vertices non-adjacent to both u and v consists of their common neighbors in Gᶜ plus the pair {u, v}, which shifts the count by 2 and completes the formula by linear arithmetic.

  1. The auxiliary function g(x, y) is symmetric: g(x, y) = g(y, x).

    Unfolding the definition of g, the result splits on whether x is adjacent to y in G. Since adjacency in a simple graph is symmetric (SimpleGraph.adj_comm), x ~ y is equivalent to y ~ x, and both branches simplify to the same value.

    lines 7–12

    uses SimpleGraph.adj_comm

      unfold seidel_matrix_compl_codegree_eq_g
      by_cases h : G.Adj x y
      · have h' : G.Adj y x := by simpa [SimpleGraph.adj_comm] using h
        simp [h, h']
      · have h' : ¬ G.Adj y x := fun hh => h (by simpa [SimpleGraph.adj_comm] using hh)
        simp [h, h']
  2. Each entry of the Seidel matrix satisfies S_{xy} = g(x, y) - [x = y].

    Unfolding the definitions of the Seidel matrix and g, we split on whether x = y. If x = y, the Seidel entry is 0 by definition; since simple graphs have no self-loops (SimpleGraph.irrefl), g(x, x) = 1, so 1 - 1 = 0. If x ≠ y, the indicator [x = y] vanishes and the definitions of S_{xy} and g(x, y) coincide.

    lines 17–21

    uses SimpleGraph.irrefl

      unfold seidel_matrix seidel_matrix_compl_codegree_eq_g
      by_cases h : x = y
      · subst h
        simp [SimpleGraph.irrefl]
      · simp [h]
  3. The sum of row x of the Seidel matrix is ∑_k S_{xk} = (∑_k g(x, k)) - 1.

    Substituting S_{xk} = g(x, k) - [x = k] from the entry formula (seidel_matrix_compl_codegree_eq_entry), the sum splits across subtraction (Finset.sum_sub_distrib). Since x belongs to the vertex set V, the sum of the indicator [x = k] over all k ∈ V evaluates to 1 (Finset.sum_ite_eq).

    lines 26–31

    uses seidel_matrix_compl_codegree_eq_entry, Finset.sum_congr, Finset.sum_sub_distrib, Finset.sum_ite_eq

      have h : ∀ k : V, seidel_matrix G x k
          = seidel_matrix_compl_codegree_eq_g G x k - (if x = k then (1:ℤ) else 0) := by
        intro k
        rw [seidel_matrix_compl_codegree_eq_entry]
      rw [Finset.sum_congr rfl (fun k _ => h k), Finset.sum_sub_distrib, Finset.sum_ite_eq]
      simp
  4. For distinct non-adjacent vertices u and v, each product summand satisfies S_{uk} S_{kv} = g(u, k) g(v, k) - [k = u] - [k = v].

    By Matrix.mul_apply, (S²)_{uv} = ∑_k S_{uk} S_{kv}. Using the entry formula and symmetry of g (seidel_matrix_compl_codegree_eq_entry, seidel_matrix_compl_codegree_eq_g_symm), S_{uk} = g(u, k) - [k = u] and S_{kv} = g(v, k) - [k = v]. When expanding the product, since u ≠ v (Ne.symm), k cannot equal both u and v. When k = u, g(v, u) = 1 because u and v are non-adjacent and graphs are loopless (SimpleGraph.irrefl, SimpleGraph.adj_comm); symmetrically, when k = v, g(u, v) = 1; when k ∉ {u, v}, both indicators vanish.

    lines 38–60

    uses Matrix.mul_apply, SimpleGraph.adj_comm, seidel_matrix_compl_codegree_eq_entry, seidel_matrix_compl_codegree_eq_g_symm, SimpleGraph.irrefl, Ne.symm

      rw [Matrix.mul_apply]
      have key : ∀ k : V, seidel_matrix G u k * seidel_matrix G k v
          = seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k
            - (if k = u then 1 else 0) - (if k = v then 1 else 0) := by
        intro k
        have hna' : ¬ G.Adj v u := fun h => hna (by simpa [SimpleGraph.adj_comm] using h)
        have hk1 : seidel_matrix G u k
            = seidel_matrix_compl_codegree_eq_g G u k - (if k = u then 1 else 0) := by
          rw [seidel_matrix_compl_codegree_eq_entry]
          by_cases h : k = u
          · simp [h]
          · simp [h, Ne.symm h]
        have hk2 : seidel_matrix G k v
            = seidel_matrix_compl_codegree_eq_g G v k - (if k = v then 1 else 0) := by
          rw [seidel_matrix_compl_codegree_eq_entry, seidel_matrix_compl_codegree_eq_g_symm]
        rw [hk1, hk2]
        by_cases h1 : k = u
        · rw [h1]
          simp [seidel_matrix_compl_codegree_eq_g, hne, hna', SimpleGraph.irrefl]
        · by_cases h2 : k = v
          · rw [h2]
            simp [seidel_matrix_compl_codegree_eq_g, Ne.symm hne, hna, SimpleGraph.irrefl]
          · simp [h1, h2]
  5. For distinct non-adjacent vertices u and v, (S²)_{uv} = (∑_k g(u, k) g(v, k)) - 2.

    Summing the pointwise identity over all k ∈ V, the sum distributes over subtraction (Finset.sum_sub_distrib). The two indicator sums ∑_k [k = u] and ∑_k [k = v] both evaluate to 1 (Finset.sum_ite_eq', Finset.mem_univ, if_true), yielding ∑_k g(u, k) g(v, k) - 1 - 1, which equals ∑_k g(u, k) g(v, k) - 2 by polynomial ring arithmetic.

    lines 61–64

    uses Finset.sum_congr, Finset.sum_sub_distrib, Finset.sum_ite_eq', Finset.mem_univ, if_true

      rw [Finset.sum_congr rfl (fun k _ => key k), Finset.sum_sub_distrib, Finset.sum_sub_distrib,
        Finset.sum_ite_eq', Finset.sum_ite_eq']
      simp only [Finset.mem_univ, if_true]
      ring
  6. Pointwise, g(u, k) + g(v, k) + g(u, k) g(v, k) = 4 · [¬ u ~ k ∧ ¬ v ~ k] - 1.

    Unfolding g, we test all four possibilities for whether u ~ k and v ~ k. If both are adjacent, (-1) + (-1) + (-1)(-1) = -1 = 4(0) - 1. If exactly one is adjacent, (-1) + 1 + (-1)(1) = -1 = 4(0) - 1. If neither is adjacent, 1 + 1 + 1 · 1 = 3 = 4(1) - 1. In every case, the identity holds.

    lines 71–72

      unfold seidel_matrix_compl_codegree_eq_g
      by_cases h1 : G.Adj u k <;> by_cases h2 : G.Adj v k <;> simp [h1, h2]
  7. ∑_k (g(u, k) + g(v, k) + g(u, k) g(v, k)) = 4 |{k | ¬ u ~ k ∧ ¬ v ~ k}| - |V|.

    Summing the pointwise identity (seidel_matrix_compl_codegree_eq_key_pointwise) over all k ∈ V (Finset.sum_congr), the sum distributes over subtraction (Finset.sum_sub_distrib). Factoring out 4 (Finset.mul_sum), the sum of indicators counts the elements satisfying ¬ u ~ k ∧ ¬ v ~ k (Finset.sum_boole), while the sum of 1 over all vertices gives |V|.

    lines 80–86

    uses seidel_matrix_compl_codegree_eq_key_pointwise, Finset.sum_congr, Finset.sum_sub_distrib, Finset.mul_sum, Finset.sum_boole

      have h : ∀ k : V, seidel_matrix_compl_codegree_eq_g G u k + seidel_matrix_compl_codegree_eq_g G v k
            + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k
          = 4 * (if (¬ G.Adj u k ∧ ¬ G.Adj v k) then (1:ℤ) else 0) - 1 :=
        fun k => seidel_matrix_compl_codegree_eq_key_pointwise G u v k
      rw [Finset.sum_congr rfl (fun k _ => h k), Finset.sum_sub_distrib, ← Finset.mul_sum,
        Finset.sum_boole]
      simp
  8. The set of common neighbors of u and v in Gᶜ is {k | ¬ u ~ k ∧ ¬ v ~ k} \ {u, v}, and {u, v} is contained in {k | ¬ u ~ k ∧ ¬ v ~ k}.

    A vertex w is a common neighbor of u and v in Gᶜ if and only if it is adjacent to both in Gᶜ (SimpleGraph.mem_commonNeighbors), which means w ≠ u, w ≠ v, ¬ u ~ w, and ¬ v ~ w (SimpleGraph.compl_adj). This matches the set difference. Moreover, because u and v are adjacent in Gᶜ, they are distinct and non-adjacent in G (SimpleGraph.adj_comm); combined with irreflexivity of adjacency (SimpleGraph.irrefl), both u and v satisfy the condition of having no edge to u or v in G.

    lines 92–108

    uses SimpleGraph.compl_adj, SimpleGraph.adj_comm, Set.mem_toFinset, SimpleGraph.mem_commonNeighbors, SimpleGraph.irrefl

      obtain ⟨hne, hna⟩ := (SimpleGraph.compl_adj G u v).mp huv
      have hna' : ¬ G.Adj v u := fun h => hna (by simpa [SimpleGraph.adj_comm] using h)
      have hset : (Gᶜ.commonNeighbors u v).toFinset
          = Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v} := by
        ext w
        simp only [Set.mem_toFinset, SimpleGraph.mem_commonNeighbors, SimpleGraph.compl_adj,
          Finset.mem_sdiff, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert,
          Finset.mem_singleton]
        tauto
      have hsub : ({u, v} : Finset V) ⊆
          Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) := by
        intro w hw
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert,
          Finset.mem_singleton] at hw ⊢
        rcases hw with rfl | rfl
        · exact ⟨SimpleGraph.irrefl G, hna'⟩
        · exact ⟨hna, SimpleGraph.irrefl G⟩
  9. The number of common neighbors of u and v in Gᶜ is |{k | ¬ u ~ k ∧ ¬ v ~ k}| - 2.

    Since {u, v} ⊆ {k | ¬ u ~ k ∧ ¬ v ~ k}, the cardinality of the difference plus |{u, v}| equals the total cardinality (Finset.card_sdiff_add_card_eq_card). Since u ≠ v, |{u, v}| = 2 (Finset.card_pair). Equating the subtype cardinality of common neighbors to the finset cardinality (Set.toFinset_card), linear arithmetic concludes that the count is reduced by 2.

    lines 109–121

    uses Finset.card_sdiff_add_card_eq_card, Finset.card_pair, Set.toFinset_card

      have h1 : (Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card
          + ({u, v} : Finset V).card
          = (Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card :=
        Finset.card_sdiff_add_card_eq_card hsub
      have h2 : ({u, v} : Finset V).card = 2 := Finset.card_pair hne
      have h3 : (Fintype.card (Gᶜ.commonNeighbors u v) : ℤ)
          = ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card : ℤ) := by
        rw [← Set.toFinset_card (Gᶜ.commonNeighbors u v), hset]
      rw [h2] at h1
      have h4 : ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card : ℤ) + 2
          = ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card : ℤ) := by
        exact_mod_cast h1
      linarith
  10. Instantiate the row sums, square entry, key sum, and complement cardinality formulas for u and v.

    From the hypothesis that u and v are adjacent in Gᶜ, we extract u ≠ v and ¬ u ~ v (SimpleGraph.compl_adj). We then specialize the row sum identities for u and v (seidel_matrix_compl_codegree_eq_row_sum), the square entry formula for (S²)_{uv} (seidel_matrix_compl_codegree_eq_sq_entry), the key sum formula (seidel_matrix_compl_codegree_eq_key_sum), and the common neighbor count in Gᶜ (seidel_matrix_compl_codegree_eq_compl_card).

    lines 129–134

    uses SimpleGraph.compl_adj, seidel_matrix_compl_codegree_eq_row_sum, seidel_matrix_compl_codegree_eq_sq_entry, seidel_matrix_compl_codegree_eq_key_sum, seidel_matrix_compl_codegree_eq_compl_card

      obtain ⟨hne, hna⟩ := (SimpleGraph.compl_adj G u v).mp huv
      have hru := seidel_matrix_compl_codegree_eq_row_sum G u
      have hrv := seidel_matrix_compl_codegree_eq_row_sum G v
      have hsq := seidel_matrix_compl_codegree_eq_sq_entry G hne hna
      have hkey := seidel_matrix_compl_codegree_eq_key_sum G u v
      have hcard := seidel_matrix_compl_codegree_eq_compl_card G huv
  11. Four times the number of common neighbors in Gᶜ equals |V| - 4 + ∑_k S_{uk} + ∑_k S_{vk} + (S²)_{uv}.

    The key sum splits into the sum of the three separate sums over g (Finset.sum_add_distrib). Substituting the row sums (∑_k g(u, k) = ∑_k S_{uk} + 1 and ∑_k g(v, k) = ∑_k S_{vk} + 1), the square entry (∑_k g(u, k) g(v, k) = (S²)_{uv} + 2), and the common neighbor count (|{k | ¬ u ~ k ∧ ¬ v ~ k}| = |Gᶜ.commonNeighbors u v| + 2), linear arithmetic over ℤ equates both sides to yield the formula.

    lines 135–142

    uses Finset.sum_add_distrib

      have hsplit : (∑ k : V, (seidel_matrix_compl_codegree_eq_g G u k
            + seidel_matrix_compl_codegree_eq_g G v k
            + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k))
          = (∑ k : V, seidel_matrix_compl_codegree_eq_g G u k)
            + (∑ k : V, seidel_matrix_compl_codegree_eq_g G v k)
            + (∑ k : V, seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k) := by
        rw [Finset.sum_add_distrib, Finset.sum_add_distrib]
      linarith
SimpleGraph.adj_comm
In a simple graph, adjacency is symmetric: u is adjacent to v if and only if v is adjacent to u.
SimpleGraph.irrefl
In a simple graph, adjacency is irreflexive: no vertex is adjacent to itself.
seidel_matrix_compl_codegree_eq_entry
The (x, y)-entry of the Seidel matrix of G equals g(x, y) - 1 if x = y, and g(x, y) if x ≠ y.
Finset.sum_congr
Two finite sums are equal if their indexing sets are equal and their summands agree on every element.
Finset.sum_sub_distrib
A sum of differences over a finite set equals the difference of the individual sums.
Finset.sum_ite_eq
Summing an indicator [a = x] b(x) over a finite set s yields b(a) if a ∈ s and 0 otherwise.
Matrix.mul_apply
The (i, k)-entry of a matrix product M N is given by the sum ∑_j M_{ij} N_{jk}.
seidel_matrix_compl_codegree_eq_g_symm
The auxiliary function g(x, y) is symmetric in its two vertex arguments.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.sum_ite_eq'
Summing an indicator [x = a] b(x) over a finite set s yields b(a) if a ∈ s and 0 otherwise.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
if_true
A conditional expression with a true condition evaluates to its then-branch.
seidel_matrix_compl_codegree_eq_key_pointwise
For any vertices u, v, k, the sum g(u, k) + g(v, k) + g(u, k) g(v, k) equals 4 · [¬ u ~ k ∧ ¬ v ~ k] - 1.
Finset.mul_sum
Multiplication by a constant distributes over a finite sum.
Finset.sum_boole
The sum of an indicator [p(x)] over a finite set s equals the cardinality of the subset of elements satisfying p.
SimpleGraph.compl_adj
Two vertices u and v are adjacent in the complement graph Gᶜ if and only if u ≠ v and u is not adjacent to v in G.
SimpleGraph.mem_commonNeighbors
A vertex belongs to the common neighbors of u and v in G if and only if it is adjacent to both u and v.
Set.mem_toFinset
An element belongs to the finset of a set if and only if it belongs to the set itself.
Finset.card_sdiff_add_card_eq_card
If s ⊆ t are finite sets, then |t \ s| + |s| = |t|.
Finset.card_pair
A finite set consisting of two distinct elements has cardinality 2.
Set.toFinset_card
The cardinality of the finset s.toFinset equals the fintype cardinality of the subtype s.
seidel_matrix_compl_codegree_eq_row_sum
The row sum ∑_k S_{xk} of the Seidel matrix of G equals (∑_k g(x, k)) - 1.
seidel_matrix_compl_codegree_eq_sq_entry
For distinct vertices u ≠ v that are not adjacent in G, the (u, v)-entry of S² equals (∑_k g(u, k) g(v, k)) - 2.
seidel_matrix_compl_codegree_eq_key_sum
The sum over all vertices k of g(u, k) + g(v, k) + g(u, k) g(v, k) equals 4 |{k | ¬ u ~ k ∧ ¬ v ~ k}| - |V|.
seidel_matrix_compl_codegree_eq_compl_card
If u and v are adjacent in Gᶜ, their number of common neighbors in Gᶜ is |{k | ¬ u ~ k ∧ ¬ v ~ k}| - 2.
Finset.sum_add_distrib
The sum of a pointwise sum of functions over a finite set equals the sum of the individual sums.

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

private def seidel_matrix_compl_codegree_eq_g {V : Type*} (G : SimpleGraph V) [DecidableRel G.Adj]    (x y : V) : ℤ := if G.Adj x y then -1 else 1private lemma seidel_matrix_compl_codegree_eq_g_symm {V : Type*} (G : SimpleGraph V)    [DecidableRel G.Adj] (x y : V) :    seidel_matrix_compl_codegree_eq_g G x y = seidel_matrix_compl_codegree_eq_g G y x := by  unfold seidel_matrix_compl_codegree_eq_g  by_cases h : G.Adj x y  · have h' : G.Adj y x := by simpa [SimpleGraph.adj_comm] using h    simp [h, h']  · have h' : ¬ G.Adj y x := fun hh => h (by simpa [SimpleGraph.adj_comm] using hh)    simp [h, h']private lemma seidel_matrix_compl_codegree_eq_entry {V : Type*} [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) :    seidel_matrix G x y = seidel_matrix_compl_codegree_eq_g G x y - (if x = y then (1:ℤ) else 0) := by  unfold seidel_matrix seidel_matrix_compl_codegree_eq_g  by_cases h : x = y  · subst h    simp [SimpleGraph.irrefl]  · simp [h]private lemma seidel_matrix_compl_codegree_eq_row_sum {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x : V) :    (∑ k : V, seidel_matrix G x k) = (∑ k : V, seidel_matrix_compl_codegree_eq_g G x k) - 1 := by  have h : ∀ k : V, seidel_matrix G x k      = seidel_matrix_compl_codegree_eq_g G x k - (if x = k then (1:ℤ) else 0) := by    intro k    rw [seidel_matrix_compl_codegree_eq_entry]  rw [Finset.sum_congr rfl (fun k _ => h k), Finset.sum_sub_distrib, Finset.sum_ite_eq]  simpprivate lemma seidel_matrix_compl_codegree_eq_sq_entry {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] {u v : V} (hne : u ≠ v) (hna : ¬ G.Adj u v) :    (seidel_matrix G * seidel_matrix G) u v      = (∑ k : V, seidel_matrix_compl_codegree_eq_g G u k *          seidel_matrix_compl_codegree_eq_g G v k) - 2 := by  rw [Matrix.mul_apply]  have key : ∀ k : V, seidel_matrix G u k * seidel_matrix G k v      = seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k        - (if k = u then 1 else 0) - (if k = v then 1 else 0) := by    intro k    have hna' : ¬ G.Adj v u := fun h => hna (by simpa [SimpleGraph.adj_comm] using h)    have hk1 : seidel_matrix G u k        = seidel_matrix_compl_codegree_eq_g G u k - (if k = u then 1 else 0) := by      rw [seidel_matrix_compl_codegree_eq_entry]      by_cases h : k = u      · simp [h]      · simp [h, Ne.symm h]    have hk2 : seidel_matrix G k v        = seidel_matrix_compl_codegree_eq_g G v k - (if k = v then 1 else 0) := by      rw [seidel_matrix_compl_codegree_eq_entry, seidel_matrix_compl_codegree_eq_g_symm]    rw [hk1, hk2]    by_cases h1 : k = u    · rw [h1]      simp [seidel_matrix_compl_codegree_eq_g, hne, hna', SimpleGraph.irrefl]    · by_cases h2 : k = v      · rw [h2]        simp [seidel_matrix_compl_codegree_eq_g, Ne.symm hne, hna, SimpleGraph.irrefl]      · simp [h1, h2]  rw [Finset.sum_congr rfl (fun k _ => key k), Finset.sum_sub_distrib, Finset.sum_sub_distrib,    Finset.sum_ite_eq', Finset.sum_ite_eq']  simp only [Finset.mem_univ, if_true]  ringprivate lemma seidel_matrix_compl_codegree_eq_key_pointwise {V : Type*} (G : SimpleGraph V)    [DecidableRel G.Adj] (u v k : V) :    seidel_matrix_compl_codegree_eq_g G u k + seidel_matrix_compl_codegree_eq_g G v k        + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k      = 4 * (if (¬ G.Adj u k ∧ ¬ G.Adj v k) then (1:ℤ) else 0) - 1 := by  unfold seidel_matrix_compl_codegree_eq_g  by_cases h1 : G.Adj u k <;> by_cases h2 : G.Adj v k <;> simp [h1, h2]private lemma seidel_matrix_compl_codegree_eq_key_sum {V : Type*} [Fintype V] (G : SimpleGraph V)    [DecidableRel G.Adj] (u v : V) :    (∑ k : V, (seidel_matrix_compl_codegree_eq_g G u k + seidel_matrix_compl_codegree_eq_g G v k        + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k))      = 4 * ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card : ℤ)        - (Fintype.card V : ℤ) := by  have h : ∀ k : V, seidel_matrix_compl_codegree_eq_g G u k + seidel_matrix_compl_codegree_eq_g G v k        + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k      = 4 * (if (¬ G.Adj u k ∧ ¬ G.Adj v k) then (1:ℤ) else 0) - 1 :=    fun k => seidel_matrix_compl_codegree_eq_key_pointwise G u v k  rw [Finset.sum_congr rfl (fun k _ => h k), Finset.sum_sub_distrib, ← Finset.mul_sum,    Finset.sum_boole]  simpprivate lemma seidel_matrix_compl_codegree_eq_compl_card {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] {u v : V} (huv : Gᶜ.Adj u v) :    (Fintype.card (Gᶜ.commonNeighbors u v) : ℤ)      = ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card : ℤ) - 2 := by  obtain ⟨hne, hna⟩ := (SimpleGraph.compl_adj G u v).mp huv  have hna' : ¬ G.Adj v u := fun h => hna (by simpa [SimpleGraph.adj_comm] using h)  have hset : (Gᶜ.commonNeighbors u v).toFinset      = Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v} := by    ext w    simp only [Set.mem_toFinset, SimpleGraph.mem_commonNeighbors, SimpleGraph.compl_adj,      Finset.mem_sdiff, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert,      Finset.mem_singleton]    tauto  have hsub : ({u, v} : Finset V) ⊆      Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) := by    intro w hw    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert,      Finset.mem_singleton] at hw ⊢    rcases hw with rfl | rfl    · exact ⟨SimpleGraph.irrefl G, hna'⟩    · exact ⟨hna, SimpleGraph.irrefl G⟩  have h1 : (Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card      + ({u, v} : Finset V).card      = (Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card :=    Finset.card_sdiff_add_card_eq_card hsub  have h2 : ({u, v} : Finset V).card = 2 := Finset.card_pair hne  have h3 : (Fintype.card (Gᶜ.commonNeighbors u v) : ℤ)      = ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card : ℤ) := by    rw [← Set.toFinset_card (Gᶜ.commonNeighbors u v), hset]  rw [h2] at h1  have h4 : ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k) \ {u, v}).card : ℤ) + 2      = ((Finset.univ.filter (fun k : V => ¬ G.Adj u k ∧ ¬ G.Adj v k)).card : ℤ) := by    exact_mod_cast h1  linarith/-- Codegree formula in the complement graph in terms of the Seidel matrix. -/theorem seidel_matrix_compl_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  obtain ⟨hne, hna⟩ := (SimpleGraph.compl_adj G u v).mp huv  have hru := seidel_matrix_compl_codegree_eq_row_sum G u  have hrv := seidel_matrix_compl_codegree_eq_row_sum G v  have hsq := seidel_matrix_compl_codegree_eq_sq_entry G hne hna  have hkey := seidel_matrix_compl_codegree_eq_key_sum G u v  have hcard := seidel_matrix_compl_codegree_eq_compl_card G huv  have hsplit : (∑ k : V, (seidel_matrix_compl_codegree_eq_g G u k        + seidel_matrix_compl_codegree_eq_g G v k        + seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k))      = (∑ k : V, seidel_matrix_compl_codegree_eq_g G u k)        + (∑ k : V, seidel_matrix_compl_codegree_eq_g G v k)        + (∑ k : V, seidel_matrix_compl_codegree_eq_g G u k * seidel_matrix_compl_codegree_eq_g G v k) := by    rw [Finset.sum_add_distrib, Finset.sum_add_distrib]  linarith
See it in the graphDiscuss this resultChallenge it