A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Matrix Tree Theorem (Kirchhoff's theorem) states that the number of spanning trees equals any cofactor of the Laplacian matrix. This remarkable result connects combinatorial counting to linear algebra, allowing computation of spanning tree counts via determinants. It has applications in electrical networks and random walk analysis.
From the graph Laplacian, you know that L = D − A, where D is the degree matrix and A is the adjacency matrix. You also know that L is positive semidefinite, that 0 is always an eigenvalue (with eigenvector 1), and that the multiplicity of the zero eigenvalue equals the number of connected components. The Matrix Tree Theorem (Kirchhoff's theorem) reveals that the nonzero eigenvalues of L encode something combinatorially concrete: the number of spanning trees of G.
The theorem has two equivalent formulations. First, the eigenvalue version: the number of spanning trees τ(G) = (1/n) · λ₁ · λ₂ · ··· · λₙ₋₁, where λ₁ ≤ λ₂ ≤ ··· ≤ λₙ₋₁ are the n − 1 nonzero eigenvalues of L. Second, the cofactor version: τ(G) equals any cofactor of L — that is, the determinant of any (n−1) × (n−1) submatrix obtained by deleting row i and column j (as long as i = j, since L is symmetric). Both formulas give the same integer. The cofactor version is usually more practical for computation: just delete one row and one column and take the determinant.
To see why this is remarkable, consider what spanning trees are: combinatorial objects (subsets of edges forming a tree on all vertices), counted by a purely algebraic operation (a determinant of a matrix derived from the graph). For a complete graph Kₙ, Cayley's formula says there are nⁿ⁻² spanning trees; the Matrix Tree Theorem recovers this result mechanically from the eigenvalues of the Laplacian. For a cycle Cₙ, each edge can be cut to form a spanning tree, giving n spanning trees — and the theorem confirms this with a 1 × 1 to (n−1) × (n−1) determinant calculation.
The physical intuition comes from electrical networks, which motivated Kirchhoff's original work. Model the graph as a resistor network with one unit resistor on each edge. The effective resistance between any two nodes involves ratios of cofactors of L. The number of spanning trees appears naturally in these resistance formulas, which is why the theorem was discovered by an electrical engineer rather than a combinatorialist. This connection to random walks is equally deep: the probability that a random walk starting at any vertex visits a particular spanning tree first (in the sense of Wilson's loop-erased random walk algorithm) is proportional to 1/τ(G), making the Matrix Tree Theorem central to sampling spanning trees uniformly at random.