AFTD Auto-Formalizing Theoretical Domains

regular_graph_compl_adj_matrix_eq_lap_matrix_sub

theoremverified

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.

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

    line 8

      ext u v
  2. Unfolding 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.

    lines 9–11

    uses SimpleGraph.lapMatrix, SimpleGraph.degMatrix, Matrix.sub_apply, Matrix.smul_apply, Matrix.one_apply, Matrix.of_apply, Matrix.diagonal_apply

      simp only [SimpleGraph.lapMatrix, SimpleGraph.degMatrix, Matrix.sub_apply,
        Matrix.smul_apply, Matrix.one_apply, Matrix.of_apply, Matrix.diagonal_apply]
      rw [hreg u]
  3. 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.

    lines 12–14

      by_cases h : u = v
      · subst h
        simp
  4. 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.

    lines 15–16

      · 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

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