Matrix-Tree Theorem

The matrix-tree theorem (Kirchhoff's theorem) provides a beautiful connection between graph theory and linear algebra, expressing the number of spanning trees as a determinant of the Laplacian matrix.

TheoremMatrix-Tree Theorem

Let $G = (V,E)$ be a graph with Laplacian matrix $L$ . For any $i \in V$ , let $L_i$ denote the matrix obtained by deleting row $i$ and column $i$ from $L$ . Then: $\tau(G) = \det(L_i)$

where $\tau(G)$ is the number of spanning trees of $G$ . Remarkably, this value is independent of the choice of $i$ .

The proof uses the Cauchy-Binet formula and properties of the incidence matrix, revealing deep structure in the Laplacian.

ProofProof Sketch

Let $B$ be the incidence matrix: rows index vertices, columns index edges, with $B_{ve} = 1$ if $v$ is incident to $e$ , and 0 otherwise.

The Laplacian can be written as $L = BB^T$ . For any vertex $i$ , let $B_i$ denote $B$ with row $i$ deleted. Then: $L_i = B_i B_i^T$

By the Cauchy-Binet formula: $\det(L_i) = \sum_{T} \det(B_i^{(T)})^2$

where the sum is over all $(n-1) \times (n-1)$ submatrices $B_i^{(T)}$ formed by selecting $n-1$ columns. The determinant $\det(B_i^{(T)})$ equals $\pm 1$ if the selected edges form a spanning tree, and 0 otherwise. Thus the sum counts spanning trees.

■

ExampleCycle Graph $C_4$

For the 4-cycle, the Laplacian is: $L = \begin{pmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{pmatrix}$

Deleting the first row and column: $L_1 = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}$

Computing: $\det(L_1) = 2(4-1) - (-1)(-2) = 6 - 2 = 4$ .

Indeed, $C_4$ has exactly 4 spanning trees (removing any one of the 4 edges yields a tree).

Remark

The matrix-tree theorem extends to weighted graphs: replace $-1$ with $-w_{ij}$ in the Laplacian. Then $\det(L_i)$ equals the sum of weights of all spanning trees, where a tree's weight is the product of its edge weights. This provides a generating function for weighted enumeration.

TheoremAll-Minors Matrix-Tree Theorem

The $(i,j)$ -cofactor of $L$ (determinant of $L$ with row $i$ and column $j$ deleted, times $(-1)^{i+j}$ ) counts spanning forests with exactly two components, where $i$ and $j$ are in different components.

The matrix-tree theorem connects to electrical networks (Kirchhoff's laws), random walks (commute times), and algebraic graph theory (spectral properties), demonstrating the unity of mathematics across seemingly disparate domains.