The Matrix-Tree Theorem From Incidence Matrices

From Incidence Matrices to a Tree Count

The Laplacian records local edge information in a matrix, but its determinant can encode a global graph count. The Matrix-Tree Theorem makes that connection precise: for a connected graph, deleting any one row and the corresponding column of the Laplacian gives a determinant equal to the number of spanning trees. The incidence-matrix factorization explains why. After applying Cauchy–Binet, the determinant becomes a sum over edge sets, and each summand is either zero or one according as the edge set fails or succeeds in forming a spanning tree.

All graphs in this tutorial are finite and simple. A tree is a connected graph with no cycle. A spanning tree of $G$ is a subgraph that is a tree and has vertex set $V(G)$. Write $t(G)$ for the number of spanning trees, following the course notation. A graph with one vertex has one spanning tree: the graph with that vertex and no edges.

Definition: Choose an orientation of every edge of $G$, meaning a choice of tail and head for each edge. The oriented incidence matrix $B$ has one row for each vertex and one column for each edge. In the column for an edge, put $-1$ at its tail, $+1$ at its head, and $0$ in every other row. The Laplacian is $L=BB^{T}$. For a vertex $r$, let $B_r$ be the matrix obtained by deleting row $r$, and let $L_r$ be the matrix obtained by deleting row $r$ and column $r$ from $L$. Thus $L_r=B_rB_r^{T}$.

Reversing an edge orientation multiplies its column of $B$ by $-1$, so it does not change $BB^T$. In the proof, it also only changes the sign of any incidence minor containing that column. The squared minors in the final sum are therefore unaffected by the orientation choices.

The Matrix-Tree Theorem

Theorem (Matrix-Tree Theorem): If $G$ is a connected graph with $n\ge 1$ vertices and $L$ is its Laplacian, then for every vertex $r$, $$ \det(L_r)=t(G). $$

Proof. First suppose $n\ge2$, and fix $r$. The matrix $B_r$ has $n-1$ rows and $m=|E(G)|$ columns, so it need not be square. Apply the standard linear-algebra Cauchy–Binet formula: for an $(n-1)$-by-$m$ matrix $A$ and an $m$-by-$(n-1)$ matrix $C$, the determinant of $AC$ is the sum, over all choices of $n-1$ indices, of the determinant of the selected columns of $A$ times the determinant of the corresponding selected rows of $C$. With $A=B_r$ and $C=B_r^T$, this gives

\det(L_r) =\det(B_rB_r^T) =\sum_{\substack{S\subseteq E(G)\\|S|=n-1}} \det(B_r[:,S])^2.

Here $B_r[:,S]$ is the square matrix formed from all rows of $B_r$ and the columns indexed by $S$. The square appears because the selected rows of $B_r^T$ form the transpose of $B_r[:,S]$, whose determinant is the same.

We now determine each term. Regard $S$ as the edge set of a subgraph on all $n$ vertices. If that subgraph is disconnected, it has a component $C$ not containing $r$. Let $y$ be the nonzero vector indexed by the rows of $B_r[:,S]$ that is $1$ at vertices in $C$ and $0$ at all other vertices. Every selected edge has both endpoints in the same component, so its incidence column has entries summing to zero on $C$. Consequently $y^TB_r[:,S]=0$. This nonzero left-null vector shows that $B_r[:,S]$ is singular, and its determinant is zero.

If the subgraph with edge set $S$ is connected, it is a tree. To justify this edge-count step, every finite connected graph has a spanning tree: while a cycle remains, delete one edge of that cycle, which preserves connectedness, and continue until no cycle remains. A tree on $n$ vertices has $n-1$ edges, as follows by induction: for $n\ge2$, an endpoint of a longest path is a leaf, and deleting that leaf and its incident edge leaves a tree. Thus a spanning tree of the connected subgraph already uses $n-1$ edges. Since $|S|=n-1$, it uses every edge of $S$, so the subgraph itself is a tree.

For a tree with edge set $S$, we claim $\det(B_r[:,S])=\pm1$. We prove this by induction on $n$. For $n=1$, the reduced matrix has no rows and no columns; its determinant is $1$ by the empty-matrix convention. Now let $n\ge2$. A tree has at least two leaves: the endpoints of a longest path must have degree one, since any additional neighbor would either extend the path or create a cycle. Choose a leaf $v\ne r$. In $B_r[:,S]$, row $v$ has a single nonzero entry, either $1$ or $-1$, in the column of its unique incident edge. Expanding the determinant along that row gives, up to sign, the determinant of the reduced incidence matrix of the tree obtained by deleting $v$ and its incident edge. This smaller graph is a tree on $n-1$ vertices and still contains $r$. By induction its reduced incidence determinant is $\pm1$. Therefore the original determinant is also $\pm1$.

We have shown that the summand is $1$ when $S$ is a spanning tree and $0$ otherwise. The sum counts exactly the spanning trees, proving the theorem for $n\ge2$. If $n=1$, connectedness and simplicity give no edges. The reduced Laplacian is the $0$-by-$0$ matrix, with determinant $1$, and there is exactly one spanning tree, the graph with its single vertex and no edges. The formula holds in this case as well. $\square$

Worked Cofactor Calculations

Worked Example: The Triangle

Let $G$ have $V=\{1,2,3\}$ and $E=\{12,23,31\}$. Its degrees are all $2$, so its Laplacian is

L= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&2 \end{pmatrix}.

Delete row and column $3$. The remaining determinant is $\det\begin{pmatrix}2&-1\\-1&2\end{pmatrix}=2\cdot2-(-1)(-1)=4-1=3$. The theorem says $t(G)=3$. Independently, any two of the three edges form a spanning tree, and there are exactly three such choices: $\{12,23\}$, $\{12,31\}$, and $\{23,31\}$. This confirms the determinant.

Worked Example: The Four-Cycle

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$. Each vertex has degree $2$. Deleting row and column $4$ from the Laplacian gives

L_4= \begin{pmatrix} 2&-1&0\\ -1&2&-1\\ 0&-1&2 \end{pmatrix}.

Expanding along the first row gives $\det(L_4)=2(2\cdot2-(-1)(-1))-(-1)((-1)\cdot2-(-1)\cdot0)=2(4-1)-2=6-2=4$. Alternatively, Cauchy–Binet sums over the four edge sets of size three. Each is obtained by omitting one cycle edge, so each is a spanning tree and contributes $1$. Thus the sum is $1+1+1+1=4$. Directly, the same four spanning trees are the four paths obtained by deleting one of the four cycle edges.

Worked Example: A Triangle with a Pendant Edge

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,13,23,34\}$. Its degrees, in vertex order $1,2,3,4$, are $2,2,3,1$. Deleting row and column $4$ gives

L_4= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&3 \end{pmatrix}.

Expanding along the first row, $\det(L_4)=2(2\cdot3-(-1)(-1))-(-1)((-1)\cdot3-(-1)(-1))+(-1)((-1)(-1)-2(-1))$. The three terms are $2(6-1)=10$, $1(-3-1)=-4$, and $-1(1+2)=-3$, so the determinant is $10-4-3=3$.

To check the count independently, every spanning tree must contain edge $34$, because it is the only edge incident to vertex $4$. It must then use exactly two of the three triangle edges, giving $\binom{3}{2}=3$ choices. Each choice connects all four vertices without a cycle. Hence $t(G)=3$, as the determinant gives.

Why the Hypotheses and Matrix Shapes Matter

Connectedness ensures that spanning trees exist and that every principal cofactor gives their count. It also ensures that the reduced incidence matrix has enough columns for the Cauchy–Binet sum to include spanning-tree edge sets. The proof specifically takes determinants of square matrices: the reduced Laplacian $L_r$, and the selected square minors $B_r[:,S]$.

For comparison, if $G$ is disconnected and has at least two vertices, then $t(G)=0$. In fact, every principal Laplacian cofactor is zero. Fix a deleted vertex $r$, choose a component $C$ not containing $r$, and let $y$ be the nonzero vector on the remaining vertices that is $1$ on $C$ and $0$ elsewhere. No edge joins $C$ to another component, so $B_r^Ty=0$. Since $L_r=B_rB_r^T$, this gives $L_ry=B_r(B_r^Ty)=0$. Thus $L_r$ is singular and $\det(L_r)=0$.

Common mistake: taking a determinant of the reduced incidence matrix. In the four-cycle example, orient the edges $12,23,34,41$ in the listed directions and delete row $4$. Then

B_4= \begin{pmatrix} -1&0&0&1\\ 1&-1&0&0\\ 0&1&-1&0 \end{pmatrix}.

This is a $3$-by-$4$ matrix, so $\det(B_4)$ is undefined. A tempting but incorrect calculation is to take its first three columns, find their determinant $-1$, and conclude that the graph has one spanning tree. That uses only one of the four minors in Cauchy–Binet. The correction is to sum the squares of all four $3$-by-$3$ minors. Each has squared determinant $1$, so $\det(B_4B_4^T)=1+1+1+1=4$, the correct spanning-tree count.

The theorem is useful because a global enumeration problem can be converted into a determinant calculation, while the proof explains why the determinant counts rather than merely correlates with spanning trees. The reduced Laplacian is always square, even though the incidence matrix usually is not; that distinction is essential both for the theorem and for its applications.

Check Your Understanding

Use the incidence-matrix proof to explain each answer, and distinguish square reduced Laplacians from rectangular reduced incidence matrices.

Why does an edge set $S$ whose subgraph is disconnected give a zero term in the Cauchy–Binet sum?
For the cycle $C_5$, how many edge subsets of size four contribute $1$, and what is the corresponding principal cofactor?
Why is the determinant of a reduced incidence matrix generally not the quantity in the Matrix-Tree Theorem?
Explain why a tree on $n$ vertices contributes exactly $1$, rather than $-1$, to the sum.
What is the spanning-tree count for the connected graph with one vertex and no edges, and how does the empty-matrix determinant convention make the theorem hold?

The Matrix-Tree Theorem From Incidence Matrices

What You'll Learn