triangle K₃
delete row/col 1: det(2 −1; −1 2)
3.
The matrix-tree theorem says the number of spanning trees of a connected graph equals any cofactor of its Laplacian matrix , where holds the vertex degrees and is the adjacency matrix.
This page is easier if you are comfortable with:
Delete one row and the matching column of the Laplacian and take the determinant (or 3 × 3 determinant) of what remains. The result counts the ways to join all the vertices with no cycles.
For the complete graph on vertices the answer is (Cayley’s formula). The theorem turns a counting problem about graphs into a determinant, which is an efficient calculation.
The eigenvalues of the Laplacian give another form: the count is the product of the non-zero eigenvalues divided by , connecting to the characteristic equation and to Perron–Frobenius ideas for networks.
The matrix-tree theorem counts the spanning trees of a graph with a determinant, avoiding the need to list them all.
Remove any one of the three edges and the other two form a spanning tree, giving 3.
These examples are worked by hand, step by step, so you can compare your own working.
Count the spanning trees of the triangle .
Count the spanning trees of a path on 3 vertices.
Count the spanning trees of the complete graph on 4 vertices.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
delete row/col 1: det(2 −1; −1 2)
3.
Cayley 4²
16.
5³
125.
spanning trees = 4
4.
The number of spanning trees equals any cofactor of the Laplacian L = D − A. For the complete graph Kₙ it is nⁿ⁻² (Cayley).
Reduced Laplacian (2 −1; −1 2).
4².
5³.
Remove one of the four edges.
A ✗
L = D − A ✓
Laplacian.
det L ✗
det L = 0, take a cofactor ✓
Singular.
complete only ✗
any connected graph ✓
General.
wrong ✗
labelled ✓
Distinct edge sets.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1296
3
1
5
16807
5
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
The number of spanning trees is any cofactor of the Laplacian.
D − A.
nⁿ⁻².
Always 0.
determinant of a 3 × 3 matrix.
Perron–Frobenius theorem.
More in Vectors and matrices and the formula sheets.