From a Laplacian to a Tree Count
A spanning tree retains every vertex of a connected graph but uses only enough edges to keep the graph connected and cycle-free. Counting these subgraphs directly can become difficult as a graph grows. The matrix-tree theorem gives a different route: build a matrix from vertex degrees and adjacencies, delete one row and the corresponding column, and take a determinant. For a finite connected graph, the result is exactly the number of spanning trees.
All graphs in this tutorial are finite and simple. A spanning tree of \(G\) is a subgraph with vertex set \(V(G)\) that is connected and has no cycles. Write \(t(G)\) for the number of spanning trees of \(G\). For a graph with at least one vertex, its Laplacian is \(\mathbf{L}(G)=\mathbf{D}(G)-\mathbf{A}(G)\), where \(\mathbf{D}(G)\) is the diagonal matrix of vertex degrees and \(\mathbf{A}(G)\) is the adjacency matrix. Thus the diagonal entry at a vertex \(v\) is \(\deg(v)\), and the entry at two distinct vertices \(u,v\) is \(-1\) if \(uv\) is an edge and \(0\) otherwise.
The cofactor is a determinant, not a signed entry of the Laplacian. The deleted row and column must have the same index. The matrix-tree theorem says that for a connected graph, any one of these principal cofactors gives the same count. The convention for the \(0\times0\) determinant handles the connected graph with a single vertex: it has one spanning tree, consisting of that vertex and no edges.
Why the Deleted Vertex Does Not Matter
Before stating the counting theorem, we can establish a useful fact about the cofactors. It concerns only the Laplacian and does not yet identify their value with a tree count.
Proof. For any vector \(x\) indexed by \(V(G)\), the definition of the Laplacian gives \[ x^{T}\mathbf{L}(G)x=\sum_{uv\in E(G)}(x_u-x_v)^2. \] Indeed, the diagonal terms contribute \(\sum_{v\in V(G)}\deg(v)x_v^2\), and each edge \(uv\) contributes \(-2x_ux_v\) from the two off-diagonal entries; grouping those terms by edge gives the displayed sum. If \(\mathbf{L}(G)x=0\), then the left side is zero. Every term on the right is nonnegative, so \(x_u=x_v\) on every edge. Since \(G\) is connected, a path joins any two vertices, and equality propagates along that path. Thus \(x\) is constant. Conversely, every constant vector is in the nullspace because each row of \(\mathbf{L}(G)\) sums to zero. The nullspace is therefore one-dimensional, so \(\mathbf{L}(G)\) has rank \(n-1\) and determinant zero.
Let \(\operatorname{adj}(\mathbf{L})\) be the adjugate, the transpose of the matrix of signed cofactors. Cofactor expansion gives \(\mathbf{L}\operatorname{adj}(\mathbf{L})=\det(\mathbf{L})\mathbf{I}=0\). Each column of the adjugate is consequently in the nullspace of \(\mathbf{L}\), so each column is constant. Also, \(\mathbf{L}\) is symmetric, and its adjugate is symmetric; hence all entries of the adjugate are the same constant. Its diagonal entries are exactly the principal cofactors \(C_r(G)\). They are therefore equal. \(\square\)
This argument explains why changing the deleted vertex does not change the determinant. The counting statement is the additional content of the matrix-tree theorem.
For a connected graph with at least two vertices, the theorem lets us choose whichever vertex makes the cofactor easiest to calculate. In the examples, each determinant will also be checked by counting spanning trees independently. That check illustrates the theorem; it is not a substitute for its general proof.
Worked Cofactor Calculations
Worked Example: The Triangle
Let \(G\) have \(V(G)=\{1,2,3\}\) and \(E(G)=\{12,23,13\}\). Each vertex has degree \(2\), and every pair of distinct vertices is adjacent, so $$ \mathbf{L}(G)= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&2 \end{pmatrix}. $$ Delete row \(3\) and column \(3\). The remaining determinant is $$ C_3(G)= \begin{vmatrix} 2&-1\\ -1&2 \end{vmatrix} =2\cdot2-(-1)(-1)=4-1=3. $$ Thus the theorem gives \(t(G)=3\).
To check this count independently, a spanning tree on these three vertices must use two edges. Omitting \(12\), \(23\), or \(13\) gives, respectively, the edge sets \(\{23,13\}\), \(\{12,13\}\), or \(\{12,23\}\); each connects all three vertices and has no cycle. These are all possibilities because a tree on three vertices has two edges. Hence the direct count is \(3\), matching the determinant.
Worked Example: A Path on Four Vertices
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\). The degrees in vertex order are \(1,2,2,1\), so $$ \mathbf{L}(G)= \begin{pmatrix} 1&-1&0&0\\ -1&2&-1&0\\ 0&-1&2&-1\\ 0&0&-1&1 \end{pmatrix}. $$ Deleting row \(4\) and column \(4\) gives $$ C_4(G)= \begin{vmatrix} 1&-1&0\\ -1&2&-1\\ 0&-1&2 \end{vmatrix}. $$ Expanding along the first row, $$ C_4(G) =1\begin{vmatrix}2&-1\\-1&2\end{vmatrix} -(-1)\begin{vmatrix}-1&-1\\0&2\end{vmatrix} =1(4-1)+1((-1)(2)-(-1)(0))=3-2=1. $$ The theorem gives \(t(G)=1\).
For an independent check, a spanning tree on four vertices needs three edges. This graph has exactly three edges, so any spanning subgraph with all four vertices and three edges must use all of them. The resulting path is connected and has no cycle. There is exactly one spanning tree, agreeing with the cofactor.
Worked Example: A Four-Cycle with a Chord
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41,13\}\). The degrees in vertex order are \(3,2,3,2\). Therefore $$ \mathbf{L}(G)= \begin{pmatrix} 3&-1&-1&-1\\ -1&2&-1&0\\ -1&-1&3&-1\\ -1&0&-1&2 \end{pmatrix}. $$ Delete row \(4\) and column \(4\). Expanding the resulting determinant along its first row gives $$ \begin{aligned} C_4(G) &=\begin{vmatrix}3&-1&-1\\-1&2&-1\\-1&-1&3\end{vmatrix}\\ &=3\bigl((2)(3)-(-1)(-1)\bigr) -(-1)\bigl((-1)(3)-(-1)(-1)\bigr) +(-1)\bigl((-1)(-1)-(2)(-1)\bigr)\\ &=3(6-1)+1(-3-1)-1(1+2)\\ &=15-4-3=8. \end{aligned} $$ The theorem gives \(t(G)=8\).
To verify the count independently, a spanning tree on four vertices has three edges, chosen from the graph’s five edges. There are \(\binom{5}{3}=10\) such edge subsets. A three-edge subset fails to be a tree exactly when it is a cycle: the only triangles in this graph have edge sets \(\{12,23,13\}\) and \(\{13,34,41\}\). There are therefore \(10-2=8\) acyclic three-edge subsets. Each is connected: an acyclic graph on four vertices with three edges has one component, since each component of a forest contributes one fewer edge than vertices. Thus all eight are spanning trees, as the determinant predicts.
What the Theorem Gives—and a Common Pitfall
The theorem is useful because a global enumeration problem becomes a determinant calculation. It also separates two facts that are easy to conflate: the Laplacian always has determinant zero, while a connected graph’s Laplacian cofactor gives its spanning-tree count. The zero determinant reflects the constant vectors in the Laplacian’s nullspace; it does not say that the graph has no spanning trees.
Common mistake: taking the determinant before deleting a row and column. For the triangle above, every row of \(\mathbf{L}(G)\) sums to zero, so the full matrix has determinant \(0\). Concluding \(t(G)=0\) would be wrong: the triangle has three spanning trees. The correction is to delete the same row and column first; deleting row \(3\) and column \(3\) gives determinant \(3\), which matches the direct count.
The connectedness hypothesis matters. A disconnected graph has no spanning tree, because no subgraph can connect vertices lying in different components. The theorem as stated uses connectedness to ensure a spanning tree exists and to give a positive cofactor. For a graph with one vertex, the convention \(t(G)=1\) agrees with the unique empty-edge spanning tree; no row or column needs to be deleted to represent this case.
When applying the result, check the setup before calculating: the graph should be finite and connected, the matrix should be its Laplacian, and the deleted row and column should correspond to the same vertex. Then compute the determinant and, for a small graph, compare it with a direct enumeration as a useful arithmetic check.
Check Your Understanding
Use the definitions and theorem to answer the questions. In each graph description, the listed edges are the entire edge set.
- For \(V(G)=\{1,2,3\}\) and \(E(G)=\{12,23\}\), form the Laplacian, delete row and column \(1\), and compute the cofactor. How many spanning trees does the graph have?
- Why is the determinant of the full Laplacian zero for every graph, and why does that fact not give the spanning-tree count of a connected graph?
- For a connected graph on at least two vertices, what does the cofactor-equality lemma establish, and what additional assertion does the matrix-tree theorem provide?
- For \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41\}\), compute a Laplacian cofactor and verify the count by listing the three-edge subsets that are spanning trees.
- State why the single-vertex graph has one spanning tree and how the \(0\times0\) determinant convention fits the theorem.