Matrix-Tree Theorem

Statement

Let $G$ be a finite connected graph on $n$ vertices with Laplacian matrix $L = D - A$ (where $D$ is the degree matrix and $A$ the adjacency matrix). Then the number of spanning trees $\tau(G)$ equals any cofactor of $L$:

where $L^{(ii)}$ is the matrix obtained by deleting row $i$ and column $i$. The result is independent of which row/column is deleted.

Visualization

$K_3$ on vertices $\{1, 2, 3\}$: every vertex has degree 2.

Delete row 3 and column 3 to get $L^{(33)}$:

The spanning trees of $K_3$: there are exactly 3, one for each omitted edge.

Tree 1: 1─2, 1─3   (omit edge 2─3)
Tree 2: 1─2, 2─3   (omit edge 1─3)
Tree 3: 1─3, 2─3   (omit edge 1─2)

$\tau(K_3) = 3 = \det(L^{(33)})$ — confirmed.

By <a class="concept-link" data-concept="Cayley's Formula ($n^{n-2}$ trees)">Cayley's Formula ($n^{n-2}$ trees), $\tau(K_n) = n^{n-2}$, so $\det(L_{K_n}^{(ii)}) = n^{n-2}$. For $n=3$: $3^1 = 3$. For $n=4$: $4^2 = 16$.

Graph	$n$	$\tau$	$\det(L^{(11)})$
$K_2$	2	1	1
$K_3$	3	3	3
$K_4$	4	16	16

Proof Sketch

1. Laplacian: $L_{ij} = \deg(i)$ if $i=j$, $-1$ if $\{i,j\} \in E$, $0$ otherwise. Note $L\mathbf{1} = 0$.
2. Matrix-tree identity: Expand $\det(L^{(ii)})$ via the Cauchy–Binet formula applied to the signed incidence matrix $B$ of $G$. The identity $L = BB^T$ (for any oriented incidence matrix $B$) reduces the cofactor to a sum over spanning trees.
3. Spanning tree terms: By the Cauchy–Binet formula, $\det(L^{(ii)}) = \sum_{T \text{ spanning tree}} (\det B_T)^2$ where $B_T$ is the submatrix of $B$ with columns indexed by $T$'s edges. Each $\det B_T = \pm 1$, so the sum equals $\tau(G)$.
4. Independence: Symmetry of the argument in $i$ shows the cofactor is the same for all $i$.

Connections

The Matrix-Tree Theorem is the algebraic proof of <a class="concept-link" data-concept="Cayley's Formula ($n^{n-2}$ trees)">Cayley's Formula ($n^{n-2}$ trees) and a flagship application of the Determinant MultiplicativityDeterminant Multiplicativity$$\det(AB) = \det(A)\,\det(B)$$The determinant of a product equals the product of determinantsRead more → identity (Cauchy–Binet). The Laplacian $L$ also features in Rank–Nullity TheoremRank–Nullity Theorem$$\operatorname{rank}(f) + \operatorname{nullity}(f) = \dim V$$The dimensions of image and kernel of a linear map sum to the domain dimensionRead more →: $\ker L$ has dimension equal to the number of connected components, proved via $\text{card\_connectedComponent\_eq\_finrank\_ker}$ in Mathlib. The spectral properties of $L$ (eigenvalues, Spectral TheoremSpectral Theorem$$A = Q \Lambda Q^T \;\text{(real symmetric case)}$$Every real symmetric matrix is orthogonally diagonalizableRead more →) underlie the algebraic connectivity (Fiedler value) used in graph partitioning.

import Mathlib.Combinatorics.SimpleGraph.LapMatrix
import Mathlib.Data.Matrix.Basic

-- Mathlib provides SimpleGraph.lapMatrix.
-- The full matrix-tree theorem is not yet in Mathlib v4.28.0;
-- we verify the K₃ cofactor directly.

-- The 2×2 submatrix of L(K₃) after deleting row/col 3:
def L33 : Matrix (Fin 2) (Fin 2) ℤ :=
  !![2, -1; -1, 2]

theorem K3_spanning_trees : L33.det = 3 := by decide