Count spanning trees with a determinant

Try

A triangle has three spanning trees, each obtained by deleting one edge. Its Laplacian matrix has diagonal entries two and off-diagonal entries minus one. Delete one row and the corresponding column: the resulting determinant is 4−1=3. The matrix-tree theorem says this determinant counts spanning trees for every finite loopless undirected graph, connecting a combinatorial object to a linear-algebraic invariant.

Predict

Predict why an arbitrary orientation can help an undirected counting problem. Give each edge a direction solely to define an incidence column with minus one at its tail and plus one at its head. Reversing an edge changes the sign of one column, but the squared determinants used in the proof do not change. The orientation is auxiliary bookkeeping, not a change to the graph being counted.

Experiment

Compare the reduced matrices of two graphs.

Graph	Reduced Laplacian	Determinant
Triangle	Rows (2,−1),(−1, 2)	3
Path on three vertices, delete an endpoint	Rows (2,−1),(−1, 1)	1

Check the path has exactly one spanning tree: itself. For a disconnected graph, predict why every full spanning-tree count is zero and why the corresponding reduced determinant must vanish.

Understand

Throughout this proof the graph is finite, undirected and loopless; parallel edges may be counted separately. Let B be the n-by-m oriented incidence matrix. Direct multiplication gives L=BBᵀ, with vertex degrees on the diagonal and negative adjacency counts off it. Delete one row of B, corresponding to a chosen root, to get B′. The same principal cofactor of L is B′B′ᵀ. By Cauchy–Binet, its determinant is the sum over all (n−1)-edge subsets S of det (B′_S)². This identity is a finite-dimensional determinant theorem; its use requires no probabilistic interpretation. It remains to identify which minors contribute.

Apply

If S contains a cycle, its oriented incidence columns are linearly dependent by a signed sum around the cycle, so the determinant is zero. If S is acyclic with n−1 edges, it is a spanning tree: a forest with c components has n−c edges, forcing c=1. For a tree, choose a leaf other than the deleted root and expand the determinant along its row. The sole nonzero entry is±1, and the remaining minor is the reduced incidence matrix of a smaller tree. Induction gives determinant±1, with the empty zero-by-zero determinant equal to one at the final stage. Therefore each spanning tree contributes exactly one and every other edge subset contributes zero.

Continue

The proof also explains weighted counting. Multiply each edge contribution by a nonnegative weight, form the weighted Laplacian, and Cauchy–Binet gives the sum over trees of the product of their edge weights. The unweighted result is the special case of all weights one. Calculating a determinant is a counting method, not an enumeration of the individual trees. For exact integer graphs, exact arithmetic avoids mistaking rounding near zero for a positive count. The linear-algebra foundation supplies determinant and rank prerequisites; the new content is the correspondence between minors and trees.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with justify greedy selection by exchange.