A connected graph on 4 vertices has Laplacian eigenvalues 0, 1, 3, and 4. How many spanning trees does it have?
A8 — multiply all nonzero eigenvalues
B3 — apply (1/n) × product of nonzero eigenvalues
C12 — the product of nonzero eigenvalues
D1 — only trees have eigenvalue products equal to n
The eigenvalue version of the Matrix Tree Theorem gives τ(G) = (1/n) × λ₁ × λ₂ × ··· × λₙ₋₁. Here n = 4 and the nonzero eigenvalues are 1, 3, 4, so τ = (1/4) × 1 × 3 × 4 = 3. Option A is wrong because you must divide by n. Option C omits the division. Option D confuses the formula with the special case of trees (where τ = 1 and the product of eigenvalues = n, but that's not a general rule).
Question 2 Multiple Choice
You want to count the spanning trees of a graph using the Matrix Tree Theorem. To compute a cofactor of L, you delete one row and one column. Which row-column pair must you choose?
ARow 1 and column 1 — the theorem only works for the top-left cofactor
BThe row and column corresponding to the highest-degree vertex
CAny row i and column i with the same index — all such cofactors are equal
DAny row i and any column j — even i ≠ j gives the spanning tree count
The Matrix Tree Theorem guarantees that all diagonal cofactors of L (deleting row i and column i for any i) give the same value τ(G). This is one of the theorem's elegant features — you can pick whichever index makes computation easiest. Option A is a common misconception; nothing is special about index 1. Option B has no basis in the theorem. Option D is wrong: off-diagonal cofactors (i ≠ j) are not guaranteed to equal τ(G); L has rank n−1, but the theorem applies to diagonal cofactors specifically.
Question 3 True / False
For a connected graph, the Matrix Tree Theorem implies that all nonzero eigenvalues of its Laplacian are strictly positive.
TTrue
FFalse
Answer: True
The Laplacian is positive semidefinite, so all eigenvalues are ≥ 0. For a connected graph, exactly one eigenvalue is 0 (the graph has one connected component), and the remaining n−1 eigenvalues are strictly positive. The Matrix Tree Theorem uses the product of these nonzero eigenvalues; if any were negative or zero (beyond the one guaranteed zero), it would break the formula. The strict positivity is a consequence of the Laplacian's spectral theory, not an assumption of the theorem.
Question 4 True / False
For any graph, different choices of which row and column to delete from the Laplacian can yield different cofactor values, so the Matrix Tree Theorem primarily approximately counts spanning trees.
TTrue
FFalse
Answer: False
This is false — all diagonal cofactors of the Laplacian are exactly equal, giving the same integer count τ(G). This is part of what makes the theorem remarkable: the result is independent of which vertex you 'ground' by deleting its row and column. The equality follows from the matrix-algebraic properties of L (it has rank n−1 with a very specific null structure), not from approximation. The theorem gives an exact count, not an estimate.
Question 5 Short Answer
Why is the Matrix Tree Theorem considered surprising, given that spanning trees are combinatorial objects and determinants are algebraic tools?
Think about your answer, then reveal below.
Model answer: It is surprising because spanning trees are discrete combinatorial structures — subsets of edges forming trees — while a determinant is a continuous algebraic operation on a real matrix. There is no obvious reason why counting a combinatorial object should reduce to computing a determinant. The connection arises because the Laplacian encodes the graph's structure, and the algebraic properties of its eigenvalues and cofactors happen to reflect the combinatorial count exactly. This bridge between combinatorics and linear algebra is the hallmark of algebraic graph theory.
The deeper reason is that the Laplacian captures both the graph's connectivity (through its null space) and its edge structure (through the degree and adjacency matrices). Spanning trees are precisely the structures that 'span' the graph without cycles, and the algebraic rank-deficiency of L (one zero eigenvalue per connected component) encodes exactly this spanning-tree structure. The theorem was first discovered through electrical network analysis by Kirchhoff, showing that the physical intuition of resistor networks gave the right combinatorial answer.