A Determinant Counts Spanning Trees
8 min read
A spanning tree keeps every vertex of a network connected using no more edges than necessary. A graph can have far too many such trees to list, so even counting them seems to require an enormous search. Kirchhoff found that their number can instead be computed with one determinant [Kirchhoff, ’47].
The reason is that this determinant already performs the counting. An identity called Cauchy–Binet expands it into one term for each candidate set of edges. Every spanning tree contributes one, and every other candidate contributes zero. The matrix calculation therefore adds up the valid trees without making us enumerate them.
Eight Trees in Five Edges
What does the count look like on a graph small enough to check by hand? Start with the four-cycle on vertices \(1,2,3,4\), then add the diagonal joining \(1\) and \(3\). A spanning tree on these four vertices has three edges. There are ten three-edge choices, but two are not trees: either triangle can be chosen while leaving the opposite vertex isolated. The other eight choices are spanning trees.
The figure shows a spanning tree in teal and, beside it, a triangle that misses vertex \(4\). The grids are their incidence minors under the orientation defined next. Whichever vertex is deleted, Kirchhoff’s determinant has to come out to \(8\) on this graph.
The Incidence Factorization
Which matrix does Kirchhoff’s determinant belong to, and does it come out to \(8\) here? Give every edge an arbitrary direction. Let \(\mathbf{B}\in\mathbb{R}^{n\times m}\) be the signed incidence matrix, with one column for each directed edge. If edge \(e\) points from vertex \(u\) to vertex \(v\), its column has \(+1\) in row \(u\), \(-1\) in row \(v\), and zero everywhere else.
The graph Laplacian is the matrix product:
\[ \mathbf{L}=\mathbf{B}\mathbf{B}^\top. \]
On the diagonal, each edge touching vertex \(u\) contributes \(1\) because its incidence entry is either \(+1\) or \(-1\). Thus \([\mathbf{L}]_{u,u}\) is the degree of \(u\). For distinct vertices \(u\) and \(v\), their rows overlap only in columns for edges between them, where the product of their two signs is \(-1\). Thus \([\mathbf{L}]_{u,v}\) is minus the number of edges between \(u\) and \(v\).
Delete the row of \(\mathbf{B}\) for one chosen vertex, which we call the root, and write the remaining matrix as \(\widetilde{\mathbf{B}}\in\mathbb{R}^{(n-1)\times m}\). Deleting the matching row and column from \(\mathbf{L}\) gives the reduced Laplacian:
\[ \widetilde{\mathbf{L}} =\widetilde{\mathbf{B}}\widetilde{\mathbf{B}}^\top. \]
For the graph in the figure, order the edges around the cycle as \((1,2),(2,3),(3,4),(4,1)\) and put the diagonal \((1,3)\) last. Use the displayed orientations and delete the row for vertex \(4\). The reduced incidence matrix is:
\[ \widetilde{\mathbf{B}} = \begin{pmatrix} 1 & 0 & 0 & -1 & 1 \\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & -1 \end{pmatrix}. \]
Multiplying it by its transpose gives the reduced Laplacian:
\[ \widetilde{\mathbf{L}} = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 3 \end{pmatrix}. \]
Its determinant can be computed without a full cofactor expansion. By multilinearity, replacing the first column by the sum of all three columns leaves the determinant unchanged because the two added determinants have repeated columns and vanish. Then subtract the first row from the third:
\[\begin{align} \det(\widetilde{\mathbf{L}}) &= \det\begin{pmatrix} 1 & -1 & -1 \\ 0 & 2 & -1 \\ 1 & -1 & 3 \end{pmatrix} \\ &= \det\begin{pmatrix} 1 & -1 & -1 \\ 0 & 2 & -1 \\ 0 & 0 & 4 \end{pmatrix} \\ &=8. \end{align}\]
The determinant matches the hand count.
Cauchy–Binet Lists the Edge Sets
How does a single determinant become a sum with one term per candidate edge set? Let \(E\) be the edge set, and let \(\widetilde{\mathbf{B}}_S\) keep the columns indexed by a set \(S\subseteq E\). Cauchy–Binet expands the incidence factorization over all sets of \(n-1\) columns, in the form used in Postnikov’s algebraic combinatorics notes [Postnikov, MIT OCW ’19]:
\[\begin{align} \det(\widetilde{\mathbf{L}}) &=\det(\widetilde{\mathbf{B}}\widetilde{\mathbf{B}}^\top) \\ &=\sum_{S\subseteq E:\,|S|=n-1} \det(\widetilde{\mathbf{B}}_S) \det(\widetilde{\mathbf{B}}_S^\top) \\ &=\sum_{S\subseteq E:\,|S|=n-1} \det(\widetilde{\mathbf{B}}_S)^2. \end{align}\]
The first line uses the incidence factorization. The second is Cauchy–Binet, with one term for each possible set of \(n-1\) columns. The last line uses that a matrix and its transpose have the same determinant.
Each term corresponds to one candidate set of \(n-1\) edges, and the incidence minor tests whether that candidate is a tree:
Lemma: For any set \(S\) of \(n-1\) edges, the incidence minor satisfies:
\[ \det(\widetilde{\mathbf{B}}_S)^2 = \begin{cases} 1, & \text{if $S$ is a spanning tree},\\ 0, & \text{otherwise}. \end{cases} \]
Proof
Suppose first that \(S\) contains a cycle. Walk once around that cycle. Give each selected incidence column a coefficient \(+1\) if its arbitrary orientation agrees with the walk and \(-1\) if it disagrees. At every vertex on the cycle, one signed column enters and one leaves, so these signed columns sum to zero. Deleting the root row preserves that dependence. Therefore the columns of \(\widetilde{\mathbf{B}}_S\) are linearly dependent, and their determinant is zero.
Now suppose that \(S\) is a spanning tree. We prove by induction on the number of vertices that its incidence minor has determinant \(+1\) or \(-1\). For two vertices, the tree has one edge. After deleting the root row, its incidence minor is the \(1\times1\) matrix \((+1)\) or \((-1)\).
For a larger tree, choose a leaf other than the deleted root. Such a leaf exists because every tree with at least two vertices has at least two leaves. The row for that leaf has exactly one nonzero entry, a \(+1\) or \(-1\) in the column of its only incident edge. Expand the determinant along that row. Removing the leaf’s row and its incident edge’s column leaves the reduced incidence matrix of the smaller tree obtained by deleting that leaf, with the same root. By induction, the smaller determinant is \(+1\) or \(-1\). The cofactor sign and the leaf’s incidence sign can only change its sign, so the original determinant is also \(+1\) or \(-1\).
Finally, consider any \(n-1\) edge set that is not a spanning tree. If it had no cycle, it would be a forest. A forest on \(n\) vertices with \(n-1\) edges has one connected component, since every added acyclic edge reduces the number of components by one. It would therefore be a spanning tree, a contradiction. Every non-tree candidate contains a cycle and falls into the zero-determinant case above.
Squaring removes the arbitrary orientation’s sign. Substituting the lemma into the Cauchy–Binet sum leaves one unit for each spanning tree and nothing for every other edge set:
\[ \det(\widetilde{\mathbf{L}}) =\#\{\text{spanning trees of the graph}\}. \]
This proves the matrix-tree theorem and shows that deleting a different row and column gives the same determinant, even though the reduced Laplacian itself changes.
Weighted Trees
What does the same determinant compute when the edges carry weights? The same proof counts trees with unequal edge weights. Give edge \(e\) a nonnegative weight \(w_e\), collect the weights in the diagonal matrix \(\mathbf{W}\), and scale incidence column \(e\) by \(\sqrt{w_e}\). The weighted reduced Laplacian factors as:
\[\begin{align} \widetilde{\mathbf{L}}_w &=(\widetilde{\mathbf{B}}\mathbf{W}^{1/2})(\widetilde{\mathbf{B}}\mathbf{W}^{1/2})^\top \\ &=\widetilde{\mathbf{B}}\mathbf{W}\widetilde{\mathbf{B}}^\top. \end{align}\]
Scaling a column scales a determinant by the same amount. Cauchy–Binet therefore turns each surviving squared minor into the product of its tree’s edge weights:
\[\begin{align} \det(\widetilde{\mathbf{L}}_w) &=\sum_{S\subseteq E:\,|S|=n-1} \det(\widetilde{\mathbf{B}}_S)^2 \prod_{e\in S} w_e \\ &=\sum_{T\text{ spanning tree}} \prod_{e\in T} w_e. \end{align}\]
The first line scales the selected incidence columns and squares their determinant. The filter lemma removes every set except the spanning trees on the second line.
With every weight equal to one, this determinant is the normalizing constant for the uniform spanning-tree distribution. More generally, it normalizes a random tree whose probability is proportional to the product of its edge weights. The uniform distribution is also volume sampling applied to the rows of \(\widetilde{\mathbf{B}}^\top\): a set of edges has nonzero squared volume exactly when it forms a tree. Scaling row \(e\) by \(\sqrt{w_e}\) gives the weighted distribution.
In an electrical network, the weights can be conductances and the determinant totals the conductance products of all tree backbones. In network reliability, spanning trees are the minimum-size edge sets that keep every vertex connected, so this weighted sum gives the lowest-order connected term when all edge survival probabilities are scaled toward zero. For a unit-conductance graph under the uniform spanning-tree distribution, an edge’s inclusion probability is its effective resistance, the graph interpretation of its leverage score.
For a graph incidence matrix, the nonzero squared minors correspond exactly to spanning trees.