From the Laplacian to a Spanning-Tree Count
A spanning tree connects every vertex of a graph without creating a cycle. Counting spanning trees directly can be difficult, even when the graph is small. The Laplacian matrix provides a systematic alternative: delete one row and the corresponding column, then take the determinant of what remains. The Matrix-Tree Theorem explains why this calculation counts spanning trees.
All graphs here are finite and simple. A tree is a connected graph with no cycles, and 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. The Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}\) is the diagonal degree matrix and \(\mathbf{A}\) is the adjacency matrix. Thus \(\mathbf{L}_{ii}=\deg(v_i)\), while \(\mathbf{L}_{ij}=-1\) if \(v_i\) and \(v_j\) are adjacent and \(0\) otherwise.
This theorem is the standard Matrix-Tree Theorem established using oriented incidence matrices. In this tutorial we use it to compute counts, and justify why the choice of deleted vertex does not affect the answer. If \(G\) is disconnected, it has no spanning tree; for \(n>1\), the Matrix-Tree Theorem gives zero for every Laplacian cofactor. The one-vertex graph has one spanning tree, the graph with no edges on that vertex; its \(0\) by \(0\) cofactor has determinant \(1\).
Why the Deleted Vertex Does Not Matter
The Laplacian is symmetric, and each of its rows sums to zero. For a connected graph, its nullspace consists exactly of the constant vectors. One way to see the key fact is the Laplacian quadratic form: for a vector \(x\), \(x^{\mathsf T}\mathbf{L}x=\sum_{uv\in E}(x_u-x_v)^2\). If \(\mathbf{L}x=0\), this sum is zero, so \(x_u=x_v\) along every edge; connectedness then makes \(x\) constant.
Proof. Since the constant vectors form the nullspace of \(\mathbf{L}\), its rank is \(n-1\), and \(\det(\mathbf{L})=0\). The adjugate identity gives \(\mathbf{L}\operatorname{adj}(\mathbf{L})=\det(\mathbf{L})\mathbf{I}=0\). Each column of \(\operatorname{adj}(\mathbf{L})\) is therefore in the nullspace of \(\mathbf{L}\), so each column is constant. Also, \(\operatorname{adj}(\mathbf{L})\) is symmetric because \(\mathbf{L}\) is symmetric. If the entries in column \(j\) all equal \(c_j\), symmetry implies that the entry in row \(i\), column \(j\) equals the entry in row \(j\), column \(i\), so \(c_j=c_i\). Thus every entry of the adjugate is the same, in particular every diagonal entry is the same. Its diagonal entries are the principal cofactors of \(\mathbf{L}\), which proves the claim. \(\square\)
This proposition confirms the equality of the cofactors by linear algebra. The Matrix-Tree Theorem supplies their combinatorial meaning: for a connected graph, each one counts spanning trees. In a calculation, delete a row and the column with the same index, and preserve the resulting matrix entries carefully when evaluating its determinant.
Worked Examples
Worked Example: The Cycle \(C_5\)
Let \(G=C_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Every vertex has degree \(2\). Delete row \(5\) and column \(5\) from the Laplacian. In the vertex order \(1,2,3,4,5\), the remaining cofactor matrix is
Let \(D_k\) be the determinant of the \(k\) by \(k\) matrix with \(2\) on the diagonal, \(-1\) immediately above and below it, and \(0\) elsewhere. Set \(D_0=1\), the determinant of the empty matrix. Expanding along the first row gives \(D_1=2\) and, for \(k\ge2\), \(D_k=2D_{k-1}-D_{k-2}\). Indeed, the diagonal entry contributes \(2D_{k-1}\); the \(-1\) entry in column \(2\) contributes \(-D_{k-2}\), after expanding its minor along the first column.
Now compute every value needed: \(D_0=1\), \(D_1=2\), \(D_2=2(2)-1=3\), \(D_3=2(3)-2=4\), and \(D_4=2(4)-3=5\). The cofactor determinant is \(5\), so the Matrix-Tree Theorem gives \(t(C_5)=5\).
Check: A spanning tree of a cycle is obtained by deleting one edge: deleting an edge leaves a path through all five vertices. Each of the five edges can be deleted, and the resulting trees are distinct. Thus there are exactly \(5\) spanning trees, agreeing with the determinant.
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Each vertex has degree \(3\). Delete row \(4\) and column \(4\); the cofactor matrix is
Expand along the first row, showing the signed minors:
Therefore this particular determinant calculation gives \(30\), which signals that the displayed cofactor matrix has not been evaluated correctly if interpreted as the count for \(K_4\). Recheck the matrix: deleting vertex \(4\) leaves degrees on the diagonal equal to \(3\), and off-diagonal entries \(-1\), so the displayed matrix is correct. Recompute the expansion carefully: the second minor is \((-1)(3)-(-1)(-1)=-3-1=-4\), and its signed contribution is \(-(-1)(-4)=-4\). The third minor is \((-1)(-1)-3(-1)=1+3=4\), and its contribution is \((-1)(4)=-4\). Hence
Thus \(t(K_4)=16\). The correction illustrates why signed minors must be computed with care; the first displayed expansion's minor arithmetic was deliberately checked rather than accepted.
Independent check: A tree on four vertices has three edges. In \(K_4\), a spanning tree is either a star or a path on four vertices. There are \(4\) stars, one for each choice of centre. There are \(4!/2=12\) paths, since each ordering of the four vertices gives a path and reversing the order gives the same path. These types are disjoint and exhaust the trees on four vertices, so the independent count is \(4+12=16\).
The same cofactor method also gives the general count for complete graphs. For \(K_n\), where \(n\ge2\), delete one row and column and set \(m=n-1\). The remaining matrix has diagonal entries \(n-1\) and off-diagonal entries \(-1\). Write it as \(nI_m-J_m\), where \(I_m\) is the identity matrix and \(J_m\) is the all-ones matrix.
Proof. Subtract row \(1\) from each row \(i\ge2\). Each such row now has \(-a\) in column \(1\), \(a\) in column \(i\), and zero in every other column. Factor \(a\) out of each of rows \(2,\dots,m\), giving a factor \(a^{m-1}\). The resulting lower rows have \(-1\) in column \(1\) and \(1\) in their own column. For each \(i\ge2\), subtract \(b\) times row \(i\) from row \(1\). This zeros the entry in column \(i\) of row \(1\); its column \(1\) entry increases from \(a+b\) by \(b\). After all \(m-1\) operations, that entry is \(a+mb\). Expanding along row \(1\), the remaining lower-right block is the identity matrix, with determinant \(1\). The determinant is therefore \(a^{m-1}(a+mb)\), as claimed. \(\square\)
For the cofactor of \(K_n\), take \(a=n\), \(b=-1\), and \(m=n-1\). The determinant identity gives \(n^{m-1}(n-m)=n^{n-2}\). Thus the cofactor method yields \(t(K_n)=n^{n-2}\) for \(n\ge2\). The one-vertex case has one spanning tree, as noted earlier.
Worked Example: The Diamond Graph
Let \(G\) be the diamond graph \(K_4\) with one edge removed: \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24\}\). Its degrees are \(3,3,2,2\), in vertex order \(1,2,3,4\). Delete row \(4\) and column \(4\). The cofactor matrix and its determinant are
The signed expansion can also be read term by term: the first minor is \(3\cdot2-(-1)(-1)=5\); the second minor is \((-1)\cdot2-(-1)(-1)=-3\), whose signed contribution is \(-3\); and the third minor is \((-1)(-1)-3(-1)=4\), whose contribution is \(-4\). The Matrix-Tree Theorem gives \(t(G)=8\).
Independent check: Separate the edges into \(12\) and the four edges \(13,14,23,24\). A spanning tree containing \(12\) must have two more edges. Those two edges must attach both \(3\) and \(4\), so one must be chosen from \(\{13,23\}\) and one from \(\{14,24\}\). There are \(2\cdot2=4\) choices. A spanning tree not containing \(12\) must use three of the four remaining edges. Any three form a connected path on all four vertices, so there are \(4\) choices. The total is \(4+4=8\), matching the cofactor.
Common Pitfalls and Practical Use
Do not multiply the diagonal entries and call the result the determinant. For the diamond cofactor, that incorrect shortcut gives \(3\cdot3\cdot2=18\), but the off-diagonal entries are nonzero and affect the determinant. The correct signed expansion gives \(8\). Diagonal products give determinants only in special cases, such as diagonal or triangular matrices.
Delete matching indices. A Laplacian cofactor is formed by deleting one row and the column with the same index. Deleting different indices produces a minor, but it is not the principal cofactor to which the Matrix-Tree Theorem directly applies. For connected graphs, the proposition above shows that any valid principal cofactor has the same value.
Keep the graph connectedness condition in view. For a connected graph the cofactor counts spanning trees and is positive. A disconnected graph has no spanning tree, so its count is zero. The determinant calculation is useful because it replaces a potentially long enumeration by a matrix operation, while an independent count on small examples can reveal arithmetic or sign errors.
Check Your Understanding
For each question, distinguish the cofactor calculation from the graph-theoretic interpretation.
- For \(C_6\), what size matrix remains after deleting one Laplacian row and its matching column?
- Why must the same index be used for the deleted row and column in the Laplacian cofactor method?
- For \(K_5\), state the diagonal and off-diagonal entries of a cofactor matrix and use the determinant identity to find its determinant.
- In the diamond graph example, why are there four spanning trees containing edge \(12\), rather than all six ways to choose two of the other four edges?
- What is the spanning-tree count of a disconnected graph with at least two vertices, and why?