A Determinant Proof Of The Matrix-Tree Theorem

From Incidence Matrices to a Tree Count

The Matrix-Tree Theorem connects a graph's spanning trees to a determinant of its Laplacian. The determinant proof explains why this connection works: after applying the Cauchy–Binet formula, the determinant becomes a sum indexed by edge sets, and each term is either zero or one. Exactly the spanning trees contribute one.

Throughout, $G=(V,E)$ is a finite simple graph with $n=|V|\geq 1$. A spanning tree is a connected, acyclic spanning subgraph; for a graph with one vertex, the graph with no edges is a spanning tree. Write $t(G)$ for the number of spanning trees. Choose an arbitrary orientation for every edge. The incidence matrix $B$ has one row for each edge and one column for each vertex: the row for an oriented edge from $u$ to $v$ has $+1$ in column $u$, $-1$ in column $v$, and zero elsewhere. The orientation is only a bookkeeping choice.

Definition: The Laplacian is $\mathbf L=\mathbf D-\mathbf A$, where $\mathbf D$ is the diagonal matrix of vertex degrees and $\mathbf A$ is the adjacency matrix. For a vertex $r$, the principal cofactor $\mathbf L^{(r)}$ is obtained by deleting row $r$ and column $r$. Let $B_r$ be the incidence matrix with column $r$ deleted.

Each row of $B$ has one $+1$ and one $-1$. Therefore $B^{T}B$ has diagonal entry $\deg(v)$ in position $v,v$, and entry $-1$ in position $u,v$ when $u$ and $v$ are adjacent, with zero for distinct nonadjacent vertices. Hence $\mathbf L=B^{T}B$, and deleting row and column $r$ gives $\mathbf L^{(r)}=B_r^{T}B_r$.

The Cauchy–Binet Expansion

Theorem (Cauchy–Binet formula): If $X$ is an $m\times k$ matrix and $Y$ is a $k\times m$ matrix, then $$ \det(YX)=\sum_{\substack{S\subseteq\{1,\ldots,m\}\\|S|=k}} \det(Y_{[:,S]})\det(X_{[S,:]}). $$ Here $Y_{[:,S]}$ selects the columns indexed by $S$, and $X_{[S,:]}$ selects the corresponding rows.

Proof. Each column of $YX$ is a linear combination of the columns of $Y$, with coefficients given by the corresponding column of $X$. Expand $\det(YX)$ using multilinearity in its $k$ columns. A term that chooses the same column of $Y$ twice has determinant zero. For a fixed set $S$ of $k$ distinct columns, the remaining terms are indexed by the possible orders in which those columns are chosen. The signed sum of their coefficients is $\det(X_{[S,:]})$, while the determinant of the chosen columns of $Y$, with their signs from reordering, supplies $\det(Y_{[:,S]})$. Summing over all such $S$ gives the formula. $\square$

Apply this formula with $X=B_r$, $Y=B_r^{T}$, and $k=n-1$. If $S$ is a set of $n-1$ edges, let $B_r[S,:]$ be the square matrix formed from their rows and the columns other than $r$. Since transposing a square matrix does not change its determinant, the two factors in each Cauchy–Binet term are equal.

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

If $m<n-1$, there are no such edge sets, so the sum is zero. The determinant expansion reduces the theorem to identifying the values of these incidence minors.

Which Edge Sets Contribute?

Lemma: For a set $S$ of $n-1$ edges, $\det(B_r[S,:])$ is zero unless $S$ is a spanning tree. If $S$ is a spanning tree, its determinant is $1$ or $-1$.

Proof. First suppose the subgraph with edge set $S$ contains a cycle. Give the edges of that cycle signs according to whether their chosen orientations agree with a traversal around the cycle. The resulting signed sum of their incidence rows is zero: at every vertex on the cycle, one traversal edge enters and one leaves. Thus the rows of $B_r[S,:]$ are linearly dependent, so its determinant is zero.

Now suppose the subgraph with edge set $S$ is acyclic. A forest on $n$ vertices with $c$ components has $n-c$ edges. To verify this count, each tree component on $q$ vertices has $q-1$ edges: this follows by induction on $q$, removing a leaf when $q\geq2$, with the one-vertex tree as the base case. Summing $q-1$ over the components gives $n-c$, including isolated vertices. Since $|S|=n-1$, we get $n-c=n-1$, so $c=1$. Therefore this acyclic subgraph is a spanning tree.

It remains to compute the determinant for a spanning tree. We use induction on $n$, with the fixed deleted vertex $r$. When $n=1$, the reduced incidence matrix is $0\times0$, whose determinant is $1$ by convention. For $n\geq2$, a tree has at least two leaves: the endpoints of a longest path are leaves, since an additional neighbor would either extend the path or create a cycle. Thus there is a leaf $\ell\neq r$. In the column of $B_r[S,:]$ indexed by $\ell$, only the row for the edge incident with $\ell$ is nonzero, and that entry is $+1$ or $-1$. Expanding the determinant along that column reduces its absolute value to the absolute value of the reduced incidence determinant for the tree obtained by removing $\ell$ and its incident edge. The induction hypothesis makes that absolute value $1$. Hence the original determinant is $1$ or $-1$. $\square$

The lemma and the expansion together give the determinant proof.

Theorem (Matrix-Tree Theorem, determinant proof): For every finite simple graph $G$ with at least one vertex and every $r\in V$, $$ \det(\mathbf L^{(r)})=t(G). $$

Proof. Every term in the Cauchy–Binet sum is the square of an integer determinant. By the lemma, it is $1$ when the selected $n-1$ edges form a spanning tree and $0$ otherwise. The sum therefore counts precisely the spanning trees of $G$. This also covers a disconnected graph: it has no spanning tree, and no $n-1$-edge subset can be a spanning tree, so every term is zero. When $n=1$, the empty edge set is the single spanning tree under our convention; the empty determinant is $1$, giving the same equality. $\square$

Worked Examples of the Expansion

Worked Example: A Triangle

Let $V=\{1,2,3\}$ and $E=\{12,23,31\}$. Orient the edges $1\to2$, $2\to3$, and $3\to1$, and delete vertex $3$. The reduced incidence matrix and Laplacian cofactor are

B_3= \begin{bmatrix} 1&-1\\ 0&1\\ -1&0 \end{bmatrix}, \qquad B_3^{T}B_3= \begin{bmatrix} 2&-1\\ -1&2 \end{bmatrix}.

The cofactor determinant is $2\cdot2-(-1)(-1)=4-1=3$. There are three two-edge subsets. For rows $12,23$, the minor is $\det\begin{bmatrix}1&-1\\0&1\end{bmatrix}=1$. For rows $12,31$, it is $\det\begin{bmatrix}1&-1\\-1&0\end{bmatrix}=-1$. For rows $23,31$, it is $\det\begin{bmatrix}0&1\\-1&0\end{bmatrix}=1$. The Cauchy–Binet sum is $1^2+(-1)^2+1^2=3$. Each pair is a spanning tree, so this agrees with the direct count: any one of the three edges can be omitted, giving three spanning trees.

Worked Example: A Triangle with a Pendant Edge

Let $V=\{1,2,3,4\}$ and $E=\{12,23,31,34\}$, oriented $1\to2$, $2\to3$, $3\to1$, and $3\to4$. Delete vertex $4$. Then $$ B_4= \begin{bmatrix} 1&-1&0\\ 0&1&-1\\ -1&0&1\\ 0&0&1 \end{bmatrix}, \qquad B_4^{T}B_4= \begin{bmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&3 \end{bmatrix}. $$ The determinant of the cofactor matrix is $2(6-1)-(-1)(-4)+(-1)(3)=10-4-3=3$.

There are four three-edge subsets. The subset $\{12,23,31\}$ gives determinant zero because its rows form the triangle cycle. The subsets $\{23,31,34\}$, $\{12,31,34\}$, and $\{12,23,34\}$ give determinants $1,-1,1$, respectively, by direct expansion of their $3\times3$ matrices. Their squared contributions total $0^2+1^2+(-1)^2+1^2=3$. These last three subsets are exactly the spanning trees: the pendant edge $34$ must be included, and one of the three triangle edges must be omitted. The direct count is also three.

Worked Example: Three Edges but No Spanning Tree

Let $V=\{1,2,3,4\}$ and $E=\{12,23,31\}$, with vertex $4$ isolated. Orient the three edges around the triangle and delete vertex $4$. The reduced incidence matrix is $$ B_4= \begin{bmatrix} 1&-1&0\\ 0&1&-1\\ -1&0&1 \end{bmatrix}. $$ There is exactly one three-edge subset, consisting of all three edges. Its incidence minor is the displayed matrix; each row sums to zero, so the rows are dependent and its determinant is zero. Thus the Cauchy–Binet sum is $0^2=0$. Independently, the graph is disconnected because vertex $4$ is isolated, so it has no spanning tree. The corresponding cofactor is the triangle Laplacian, whose rows sum to zero; its determinant is likewise zero.

Why the Proof Works and a Common Pitfall

The crucial feature is the square in the Cauchy–Binet expansion. A spanning tree's reduced incidence determinant may be $1$ or $-1$, depending on the edge orientations and row order, but squaring removes that sign. Cycles create row dependence, while a forest with $n-1$ edges must be connected. Consequently the expansion does not require finding or ordering spanning trees in advance: the algebra itself assigns one unit to each tree and zero to every other edge subset.

Common mistake: overlooking the subset of all edges. If a graph has exactly three edges and $n-1=3$, it has one three-edge subset, not zero three-edge subsets. In the disconnected example above, that one subset is the whole edge set. Its minor is singular, so its contribution is zero. The correct conclusion is not that the Cauchy–Binet sum is empty, but that its only term is zero. Keeping the index set and the value of each term separate prevents this counting error.

Another useful check is to distinguish the full Laplacian from a cofactor. Every row of $\mathbf L$ sums to zero, so its determinant is zero; the theorem concerns the determinant after deleting one row and the corresponding column. The single-vertex case is also worth keeping in view: its cofactor is the empty determinant $1$, matching its one spanning tree under the stated convention.

Check Your Understanding

Use the incidence-minor expansion, and state which edge subsets contribute.

For $V=\{1,2,3,4\}$, $E=\{12,23,34\}$, how many terms appear in the expansion for a cofactor, and which one contributes?
Explain why the rows corresponding to a cycle are linearly dependent, regardless of the chosen edge orientations.
Why must an acyclic edge set of size $n-1$ on $n$ vertices be connected, even when isolated vertices are allowed?
For the triangle $V=\{1,2,3\}$, $E=\{12,23,31\}$, verify the three reduced-incidence $2\times2$ determinants using a different orientation of one edge. What changes, and what stays the same?
For a one-vertex graph, identify the incidence matrix, its reduced matrix, the cofactor determinant, and the spanning-tree count.