Kirchhoff’s Matrix Tree Theorem
Counting Spanning Trees
You have a graph. You want to know: how many distinct spanning trees does it have?
For a complete graph \(K_4\), you could enumerate them by hand. For a cycle \(C_5\), you might try brute force. But for a general graph with 50 vertices and 200 edges, enumeration is hopeless.
Kirchhoff's Matrix Tree Theorem gives you the exact count using linear algebra — one matrix, one determinant, one number.
The Laplacian Matrix
Given a graph \(G\) with \(n\) vertices, define the Laplacian matrix \(L\) as:
where: - \(D\) is the degree matrix — a diagonal matrix where \(D_{ii} = \deg(i)\) - \(A\) is the adjacency matrix — \(A_{ij} = 1\) if there's an edge between \(i\) and \(j\)
In other words:
The Laplacian has a key property: every row and column sums to zero. This means \(\det(L) = 0\) always. So you don't take the determinant of \(L\) itself.
The Theorem
Kirchhoff's Matrix Tree Theorem: The number of spanning trees of \(G\) equals any cofactor of \(L\). That is, delete any row \(i\) and column \(i\) from \(L\), and take the determinant of the resulting \((n-1) \times (n-1)\) matrix.
It doesn't matter which row and column you delete — all cofactors are equal (a consequence of the row-sum-zero property).
Example 1: Complete Graph \(K_4\)
\(K_4\) has vertices \(\{0, 1, 2, 3\}\) and all 6 possible edges.
Adjacency matrix:
Degree matrix: Every vertex has degree 3.
Laplacian \(L = D - A\):
Delete row 0 and column 0:
Compute \(\det(L')\):
Number of spanning trees of \(K_4\): 16.
Sanity check: Cayley's formula gives \(4^{4-2} = 4^2 = 16\). Matches.
Example 2: Cycle \(C_5\)
\(C_5\) has vertices \(\{0, 1, 2, 3, 4\}\) with edges forming a cycle: \((0,1), (1,2), (2,3), (3,4), (4,0)\).
Every vertex has degree 2. The Laplacian:
Delete row 0 and column 0:
This is a tridiagonal matrix. Expanding the determinant (or using the recurrence for tridiagonal determinants):
Number of spanning trees of \(C_5\): 5.
This makes sense: a spanning tree of a cycle on \(n\) vertices is obtained by removing exactly one edge, and there are \(n\) edges to choose from. So \(C_n\) has exactly \(n\) spanning trees.
The Connection to Cayley
Kirchhoff's theorem applied to \(K_n\) gives \(n^{n-2}\) — Cayley's formula. This is another proof of Cayley's formula, entirely different from the Prufer sequence bijection.
The eigenvalues of the Laplacian of \(K_n\) are \(0\) (with multiplicity 1) and \(n\) (with multiplicity \(n-1\)). The number of spanning trees equals \(\frac{1}{n}\prod_{\lambda_i \neq 0} \lambda_i = \frac{1}{n} \cdot n^{n-1} = n^{n-2}\).
The Code
double computeDeterminant(vector<vector<double>>& matrix, int size) {
double det = 1.0;
for (int col = 0; col < size; col++) {
int pivotRow = col;
for (int row = col + 1; row < size; row++) {
if (abs(matrix[row][col]) > abs(matrix[pivotRow][col])) {
pivotRow = row;
}
}
swap(matrix[col], matrix[pivotRow]);
if (pivotRow != col) det *= -1.0;
if (abs(matrix[col][col]) < 1e-9) return 0.0;
det *= matrix[col][col];
for (int row = col + 1; row < size; row++) {
double factor = matrix[row][col] / matrix[col][col];
for (int k = col; k < size; k++) {
matrix[row][k] -= factor * matrix[col][k];
}
}
}
return det;
}
long long countSpanningTrees(int numVertices, vector<pair<int,int>>& edges) {
vector<vector<double>> laplacian(numVertices, vector<double>(numVertices, 0.0));
for (auto [u, v] : edges) {
laplacian[u][v] -= 1.0;
laplacian[v][u] -= 1.0;
laplacian[u][u] += 1.0;
laplacian[v][v] += 1.0;
}
int reducedSize = numVertices - 1;
vector<vector<double>> cofactorMatrix(reducedSize, vector<double>(reducedSize));
for (int i = 0; i < reducedSize; i++) {
for (int j = 0; j < reducedSize; j++) {
cofactorMatrix[i][j] = laplacian[i + 1][j + 1];
}
}
double det = computeDeterminant(cofactorMatrix, reducedSize);
return llround(det);
}
Complexity: \(O(n^3)\) for Gaussian elimination on the \((n-1) \times (n-1)\) matrix. Space: \(O(n^2)\).
When Is This Useful?
Most tree problems don't need Kirchhoff. But when you see a problem that asks "how many spanning trees does this graph have?" or "count the number of labeled spanning trees with certain edge constraints," the matrix tree theorem is the only efficient approach.
Kirchhoff's theorem connects graph theory to linear algebra. The combinatorial quantity (number of spanning trees) equals an algebraic quantity (determinant of a submatrix). This is one of the deepest connections in discrete mathematics.
For contest problems, the typical use case is: build the Laplacian, take the cofactor determinant modulo a prime (using modular Gaussian elimination instead of floating point), and output the result.
Try It
Fill in countSpanningTrees in the starter code.
Input: K4 (4 vertices, 6 edges)
Output: 16
Input: C5 (5 vertices, 5 edges forming a cycle)
Output: 5
Predict before running: How many spanning trees does a tree itself have? Exactly 1 — the tree IS the only spanning tree. The Laplacian cofactor confirms this: the determinant is 1 for any tree.
Challenge: How many spanning trees does the Petersen graph have? (10 vertices, 15 edges.) Build the Laplacian and compute. The answer is 2000.
Edge Cases to Watch For
- Graph is disconnected: No spanning tree exists. The cofactor determinant equals 0, but floating-point Gaussian elimination may return a small nonzero value due to rounding. Check if the result is close to zero and round accordingly.
- Floating-point precision: Gaussian elimination on doubles accumulates rounding errors. For large matrices, the determinant can drift significantly. Use
llround()on the final result, or use modular arithmetic (Gaussian elimination mod a prime) for exact answers. - Multi-edges between the same pair of vertices: The Laplacian matrix entry \(L[u][v]\) must reflect the number of parallel edges (not just 0/1). If your code builds the Laplacian assuming simple graphs, multi-edges are silently collapsed and the count is wrong.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CF determinant problems | Various Codeforces problems involving matrix-tree theorem | Hard |
| SPOJ MKMTRX — Matrix Tree | spoj.com/problems/MKMTRX | Hard |
| LC 823 — Binary Trees With Factors | leetcode.com/problems/binary-trees-with-factors | Medium |
| LC 1339 — Max Product of Splitted BT | leetcode.com/problems/maximum-product-of-splitted-binary-tree | Medium |
What's Next?
You've completed the entire Tree Algorithms course -- from basic traversals to Kirchhoff's theorem. Every tree technique in competitive programming is now in your toolkit. Go solve problems.