AFTD Auto-Formalizing Theoretical Domains

simple_graph_laplacian_matrix_isHermitian

theoremverifiedformalization

The Laplacian matrix of any finite simple graph is Hermitian.

Statement

lemma simple_graph_laplacian_matrix_isHermitian {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    (simple_graph_laplacian_matrix G).IsHermitian
Formalizes
arXiv:2611.03879, Section 1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For every finite type V with decidable equality and every simple graph G on V with decidable adjacency, the Laplacian matrix of G (defined over the real numbers as the diagonal matrix of vertex degrees minus the adjacency matrix of G) is Hermitian (i.e., equal to its conjugate transpose).

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

By definition, the Laplacian matrix of a graph is the difference D - A of its diagonal degree matrix and its real adjacency matrix. Over the real numbers, a matrix is Hermitian if and only if it is symmetric. Because diagonal matrices are symmetric, adjacency matrices of undirected graphs are symmetric, and the difference of symmetric matrices is symmetric, the Laplacian is Hermitian. Mathlib's simplifier proves this automatically upon unfolding the definition.

  1. The Laplacian matrix of a finite simple graph G is Hermitian. automation

    Unfolding the definition of the Laplacian matrix expresses it as D - A, where D is the diagonal matrix of vertex degrees and A is the adjacency matrix of G over ℝ. For real matrices, being Hermitian is equivalent to being symmetric. Mathlib's simplifier reduces the goal to True using the facts that any diagonal matrix is symmetric, the adjacency matrix of an undirected simple graph is symmetric, and the difference of two symmetric matrices is symmetric.

    line 4

    uses is_tree_induce_compl_singleton

        (simple_graph_laplacian_matrix G).IsHermitian := by first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton | (simp only [simple_graph_laplacian_matrix] at *; first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton)
is_tree_induce_compl_singleton
Removing a vertex of degree 1 (a leaf) from a tree yields an induced subgraph that is still a tree.

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 Laplacian matrix of a finite simple graph is Hermitian (real symmetric). -/lemma simple_graph_laplacian_matrix_isHermitian {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    (simple_graph_laplacian_matrix G).IsHermitian := by first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton | (simp only [simple_graph_laplacian_matrix] at *; first | exact is_tree_induce_compl_singleton | (apply is_tree_induce_compl_singleton <;> assumption) | (apply is_tree_induce_compl_singleton <;> simp_all) | simpa using is_tree_induce_compl_singleton)
See it in the graphDiscuss this resultChallenge it