seidel_matrix_compl_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 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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- 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.
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.
uses
SimpleGraph.adj_communfold 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']
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.
uses
SimpleGraph.irreflunfold seidel_matrix seidel_matrix_compl_codegree_eq_g by_cases h : x = y · subst h simp [SimpleGraph.irrefl] · simp [h]
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).
uses
seidel_matrix_compl_codegree_eq_entry,Finset.sum_congr,Finset.sum_sub_distrib,Finset.sum_ite_eqhave 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
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.
uses
Matrix.mul_apply,SimpleGraph.adj_comm,seidel_matrix_compl_codegree_eq_entry,seidel_matrix_compl_codegree_eq_g_symm,SimpleGraph.irrefl,Ne.symmrw [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]
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.
uses
Finset.sum_congr,Finset.sum_sub_distrib,Finset.sum_ite_eq',Finset.mem_univ,if_truerw [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
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.
unfold seidel_matrix_compl_codegree_eq_g by_cases h1 : G.Adj u k <;> by_cases h2 : G.Adj v k <;> simp [h1, h2]
∑_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|.
uses
seidel_matrix_compl_codegree_eq_key_pointwise,Finset.sum_congr,Finset.sum_sub_distrib,Finset.mul_sum,Finset.sum_boolehave 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
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.
uses
SimpleGraph.compl_adj,SimpleGraph.adj_comm,Set.mem_toFinset,SimpleGraph.mem_commonNeighbors,SimpleGraph.irreflobtain ⟨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⟩
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.
uses
Finset.card_sdiff_add_card_eq_card,Finset.card_pair,Set.toFinset_cardhave 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
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).
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_cardobtain ⟨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
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.
uses
Finset.sum_add_distribhave 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.
- The proof defines an auxiliary function g(x, y) taking values -1 for adjacent pairs and +1 for non-adjacent pairs (including on the diagonal), which differs from the Seidel matrix S only at the diagonal entries where S_{xx} = 0 while g(x, x) = 1.
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.
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