regular_graph_compl_adj_matrix_eq_lap_matrix_sub
For any d-regular graph G on a finite vertex set V, the adjacency matrix of its complement Gᶜ equals G.lapMatrix ℝ - ((d+1)I - J), where J is the all-ones matrix.
Statement
open scoped Classical in theorem regular_graph_compl_adj_matrix_eq_lap_matrix_sub {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) (hreg : G.IsRegularOfDegree d) : Gᶜ.adjMatrix ℝ = G.lapMatrix ℝ - ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ))
- Source
- arXiv:2610.36127 Proof of Lemma 35
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any finite type $V$, any natural number $d$, and any simple graph $G$ on $V$, if $G$ is regular of degree $d$ (that is, every vertex in $G$ has degree $d$), then the adjacency matrix of the complement graph $G^c$ over the real numbers $\mathbb{R}$ is equal to the Laplacian matrix of $G$ over $\mathbb{R}$ minus the quantity $((d + 1) I - J)$, where $I$ is the identity matrix on $V$ over $\mathbb{R}$ and $J$ is the all-ones matrix on $V \times V$ over $\mathbb{R}$.
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 proceeds by comparing entries at arbitrary vertices u and v. After unfolding the definition of the Laplacian L(G) = D(G) - A(G) and using d-regularity to substitute d for the degree of each vertex, the verification splits into diagonal entries (u = v) and off-diagonal entries (u ≠ v). On the diagonal, both sides evaluate to 0 because simple graphs have no self-loops; off the diagonal, the identity reduces to A(Gᶜ)_{u,v} = 1 - A(G)_{u,v}, which holds by definition of the graph complement.
It suffices to show that the entries of both matrices agree at every pair of vertices u and v.
By matrix extensionality, two matrices of the same dimension are equal if and only if their (u, v)-entries are equal for all vertices u and v.
ext u vUnfolding matrix operations and using d-regularity expresses the (u, v)-entry of the right-hand side in terms of u = v and G's adjacency matrix.
We expand the definitions of the Laplacian matrix L(G) = D(G) - A(G) and the degree matrix D(G), as well as entrywise matrix subtraction, scalar multiplication, the identity matrix, and the all-ones matrix. Then, since G is d-regular, we rewrite the degree of u as d.
uses
SimpleGraph.lapMatrix,SimpleGraph.degMatrix,Matrix.sub_apply,Matrix.smul_apply,Matrix.one_apply,Matrix.of_apply,Matrix.diagonal_applysimp only [SimpleGraph.lapMatrix, SimpleGraph.degMatrix, Matrix.sub_apply, Matrix.smul_apply, Matrix.one_apply, Matrix.of_apply, Matrix.diagonal_apply] rw [hreg u]
The matrix equality holds for diagonal entries (u = v).
We consider the case u = v. For any simple graph, there are no self-loops, so the diagonal entries of both the complement's adjacency matrix and G's adjacency matrix are 0. The right-hand side simplifies to d - 0 - ((d + 1) · 1 - 1) = 0, matching the left-hand side.
by_cases h : u = v · subst h simp
The matrix equality holds for off-diagonal entries (u ≠ v).
When u ≠ v, the conditions u = v evaluate to false, simplifying the right-hand side to -A(G)_{u,v} + 1. Since complement adjacency is the negation of adjacency for distinct vertices, the left-hand side is 1 if u and v are not adjacent in G and 0 if they are. Splitting into whether (u, v) is an edge of G yields 0 = -1 + 1 and 1 = 0 + 1, both verified by ring arithmetic.
· simp [h] split_ifs <;> ring
SimpleGraph.lapMatrix- The Laplacian matrix of a graph is the degree matrix minus the adjacency matrix.
SimpleGraph.degMatrix- The degree matrix of a graph is the diagonal matrix with the vertex degrees along the diagonal.
Matrix.sub_apply- The (i, j)-th entry of the difference of two matrices is the difference of their (i, j)-th entries.
Matrix.smul_apply- The (i, j)-th entry of a scalar-multiplied matrix is the scalar times the (i, j)-th entry.
Matrix.one_apply- The (i, j)-th entry of the identity matrix is 1 if i = j and 0 otherwise.
Matrix.of_apply- The (i, j)-th entry of a matrix defined by a function is the function applied to (i, j).
Matrix.diagonal_apply- The (i, j)-th entry of a diagonal matrix is the specified value on the diagonal and 0 off the diagonal.
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.
open scoped Classical in/-- The adjacency matrix of the complement of a d-regular graph equals L(G) - ((d+1)I - J). -/theorem regular_graph_compl_adj_matrix_eq_lap_matrix_sub {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) (hreg : G.IsRegularOfDegree d) : Gᶜ.adjMatrix ℝ = G.lapMatrix ℝ - ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) := by ext u v simp only [SimpleGraph.lapMatrix, SimpleGraph.degMatrix, Matrix.sub_apply, Matrix.smul_apply, Matrix.one_apply, Matrix.of_apply, Matrix.diagonal_apply] rw [hreg u] by_cases h : u = v · subst h simp · simp [h] split_ifs <;> ring