From Laplacian Cofactors to Eigenvalues
The Matrix-Tree theorem turns a determinant into a spanning-tree count. The spectral version expresses the same count using the eigenvalues of the graph Laplacian. Its practical advantage is that it connects a global counting quantity—the number of spanning trees—to the full Laplacian spectrum. The key is to compare two ways of finding one coefficient of a determinant.
Throughout, \(G=(V,E)\) is a finite simple graph with \(n=|V|\geq 1\). The Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}\) is the diagonal degree matrix and \(\mathbf{A}\) is the adjacency matrix. A spanning tree is a subgraph containing all vertices that is connected and has no cycles; \(t(G)\) denotes the number of spanning trees. We use the convention that the product over an empty set of numbers is \(1\).
Connectedness matters: for a connected graph, zero is a Laplacian eigenvalue of multiplicity one, and every other eigenvalue is positive. These facts follow from the Laplacian quadratic form and the characterization of its nullspace. The theorem below uses the earlier Matrix-Tree theorem in its cofactor form: for a connected graph, deleting the same row and column from \(\mathbf{L}\) gives a determinant equal to \(t(G)\).
Proof by Comparing Determinant Coefficients
First consider the polynomial \(p(x)=\det(\mathbf{L}+x\mathbf{I})\), where \(\mathbf{I}\) is the \(n\)-by-\(n\) identity matrix. The spectral theorem for real symmetric matrices gives an orthonormal eigenbasis for \(\mathbf{L}\). In that basis, \(\mathbf{L}+x\mathbf{I}\) has diagonal entries \(x+\lambda_1,\ldots,x+\lambda_n\). Thus the coefficient of \(x\) in \(p(x)\) is \(\prod_{i=2}^n\lambda_i\), since \(\lambda_1=0\).
We can also find that coefficient directly from the determinant. In the determinant expansion, a term contributing exactly one factor \(x\) chooses \(x\) from one diagonal entry and entries of \(\mathbf{L}\) for all the remaining rows and columns. Summing over which diagonal entry supplies \(x\) gives the sum of the \(n\) principal minors of \(\mathbf{L}\) of order \(n-1\). Each such minor is a cofactor obtained by deleting one row and the corresponding column. By the cofactor form of the Matrix-Tree theorem, each equals \(t(G)\). Therefore the coefficient is \(n\,t(G)\). Equating the two expressions proves the formula.
Proof. Since \(\mathbf{L}\) is real and symmetric, its eigenvalues are real and its determinant polynomial satisfies $$ \det(\mathbf{L}+x\mathbf{I})=\prod_{i=1}^{n}(x+\lambda_i). $$ With \(\lambda_1=0\), the coefficient of \(x\) on the right is \(\prod_{i=2}^{n}\lambda_i\). By expanding the determinant on the left, the coefficient of \(x\) is the sum of the principal minors of \(\mathbf{L}\) of order \(n-1\): choosing \(x\) in position \(j\) leaves the determinant of the matrix obtained by deleting row \(j\) and column \(j\). There are \(n\) such minors, and each is \(t(G)\) by the Matrix-Tree theorem. The coefficient is therefore \(n\,t(G)\). Equating coefficients gives \(\prod_{i=2}^{n}\lambda_i=n\,t(G)\), as required. When \(n=1\), the product has no factors and equals \(1\); the sole cofactor is the determinant of the empty matrix, also \(1\), so the same identity gives \(t(G)=1\). \(\square\)
Worked Examples
Worked Example: The Triangle
Let \(G\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,23,31\}\), so \(G=C_3\). Its Laplacian is $$ \mathbf{L}= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&2 \end{pmatrix}. $$ The all-ones vector \((1,1,1)\) has eigenvalue \(0\), since every row sums to \(0\). If \(x=(a,b,c)\) satisfies \(a+b+c=0\), then the first coordinate of \(\mathbf{L}x\) is \(2a-b-c=3a\); the second is \(-a+2b-c=3b\); and the third is \(-a-b+2c=3c\). The subspace defined by \(a+b+c=0\) has dimension \(2\), so the other two eigenvalues are both \(3\).
The formula gives \(t(G)=(3\cdot3)/3=9/3=3\). Independently, a spanning tree of the triangle is obtained by deleting one of its three edges, giving exactly \(3\) choices.
Check: the spectral count \(9/3=3\) agrees with the direct count. Each of the three choices leaves a path on all three vertices, so each is connected and acyclic.
Worked Example: The Star \(K_{1,4}\)
Let \(G\) have vertex set \(V=\{0,1,2,3,4\}\) and edge set \(E=\{01,02,03,04\}\). Vertex \(0\) is the center. In this vertex order, the Laplacian is $$ \mathbf{L}= \begin{pmatrix} 4&-1&-1&-1&-1\\ -1&1&0&0&0\\ -1&0&1&0&0\\ -1&0&0&1&0\\ -1&0&0&0&1 \end{pmatrix}. $$ The all-ones vector has eigenvalue \(0\). For any vector whose center coordinate is \(0\) and whose four leaf coordinates sum to \(0\), multiplication by \(\mathbf{L}\) leaves the vector unchanged: the center coordinate of the product is the negative of that leaf sum, hence \(0\), and each leaf coordinate is unchanged. This subspace has dimension \(3\), giving eigenvalue \(1\) with multiplicity \(3\). The vector \((-4,1,1,1,1)\) has center coordinate \(-20\) after multiplication, and each leaf coordinate \(5\); these are the coordinates of \(5(-4,1,1,1,1)\). Thus the remaining eigenvalue is \(5\).
The eigenvalues are \(0,1,1,1,5\), so \(t(G)=(1\cdot1\cdot1\cdot5)/5=5/5=1\). Directly, all four edges must belong to a spanning subgraph that connects every leaf to the center. The graph itself is a tree, so there is exactly one spanning tree.
Check: the computed eigenvalues account for all five dimensions, and the product of the four nonzero eigenvalues is \(5\). Dividing by the order \(5\) gives the direct count \(1\).
Worked Example: The Complete Graph \(K_4\)
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24,34\}\). Each vertex has degree \(3\), and the adjacency matrix has \(0\) on its diagonal and \(1\) elsewhere. Hence \(\mathbf{L}=4\mathbf{I}-\mathbf{J}\), where \(\mathbf{J}\) is the \(4\)-by-\(4\) all-ones matrix. The all-ones vector has eigenvalue \(0\). If the coordinates of \(x\) sum to \(0\), then \(\mathbf{J}x=0\), so \(\mathbf{L}x=4x\). The sum-zero subspace has dimension \(3\), giving the spectrum \(0,4,4,4\).
The spectral formula gives \(t(G)=(4\cdot4\cdot4)/4=64/4=16\). To check this independently, a spanning tree on four vertices has three edges. There are \(\binom{6}{3}=20\) three-edge subsets of \(E\). Exactly four are triangles, one for each choice of the isolated fourth vertex, and none is a spanning tree. Any disconnected three-edge subset must be a triangle together with an isolated vertex: if the components had sizes \(2\) and \(2\), they could contain at most two edges in total. Every other three-edge subset is connected and therefore a tree. The direct count is \(20-4=16\).
Check: the spectral product is \(64\), and division by the four vertices gives \(16\), matching the independent count of \(16\) spanning trees.
Interpreting and Checking the Formula
The division by \(n\) is essential. The product of the nonzero eigenvalues is not itself the spanning-tree count; it is \(n\) times that count. One way to remember the factor is the proof: there are \(n\) principal cofactors, each equal to the same spanning-tree count, and the coefficient calculation adds all of them.
The formula assumes that the graph is connected. If a graph has more than one connected component, its Laplacian has more than one zero eigenvalue, and it has no spanning tree. The connected formula is not applied in that situation. For a connected graph with one vertex, the nonzero-eigenvalue product has no factors; with the empty-product convention, it is \(1\), which is the count of the unique spanning tree consisting of that vertex and no edges.
Common Mistake: Accepting Impossible Spectral Data
Suppose someone claims that a connected graph with \(n=5\) has nonzero Laplacian eigenvalues \(1,2,3,4\). Substitution into the formula gives $$ \frac{1\cdot2\cdot3\cdot4}{5}=\frac{24}{5}. $$ This cannot be the spanning-tree count of a graph, because a spanning-tree count is an integer. The calculation does not describe a graph with a fractional number of spanning trees; instead, it shows that the proposed eigenvalue data cannot be the nonzero Laplacian spectrum of a connected graph on five vertices.
For comparison, the star \(K_{1,4}\) has nonzero Laplacian eigenvalues \(1,1,1,5\), as computed above. Their product is \(1\cdot1\cdot1\cdot5=5\), and \(5/5=1\), consistent with its direct spanning-tree count. Integrality is a useful necessary check on proposed spectral data, although an integer result alone does not prove that the data come from a graph.
Check Your Understanding
For each question, state the relevant assumption and show the calculation or reasoning used.
- Why does the coefficient of \(x\) in \(\det(\mathbf{L}+x\mathbf{I})\) equal the sum of the principal minors of order \(n-1\)?
- A connected graph has \(n=4\) and nonzero Laplacian eigenvalues \(2,2,4\). What spanning-tree count does the spectral formula give?
- Explain why the spectrum \(0,1,2,3\) cannot be the Laplacian spectrum of a connected graph on four vertices.
- For the one-vertex graph, identify its spanning tree and explain how the empty-product convention makes the formula work.
- Why would the connected spectral formula not apply to a graph with two connected components?