Skip to content
Tutorials Center
My learning

Topics

Lesson 141 of 225 ยท Shortest Paths and Spanning Trees

Counting Spanning Trees: Kirchhoff, Cayley, Prufer and Reverse-Delete

Count spanning trees with Kirchhoff's matrix-tree theorem and Cayley's formula, encode labelled trees as Prufer sequences, and build an MST with reverse-delete in Python.

In minimum spanning trees you looked for the cheapest tree that connects a graph. This lesson asks a different question: how many spanning trees does a graph have? The answer is useful for network reliability (more spanning trees means more ways to stay connected), for chemistry and physics (counting configurations), and it connects graph theory to linear algebra.

You will meet three tools: Kirchhoff's matrix-tree theorem for any graph, Cayley's formula for the complete graph, and Prufer sequences, a beautiful code that turns labelled trees into plain lists. The lesson closes with the reverse-delete algorithm, a third way (after Kruskal and Prim) to build a minimum spanning tree.

Kirchhoff's matrix-tree theorem

Build the Laplacian matrix L of an undirected graph with n vertices: put the degree of vertex i on the diagonal, and -1 at L[i][j] when i and j are joined by an edge (-k for k parallel edges), 0 otherwise. Every row sums to 0.

Theorem. Delete any one row and the matching column. The determinant of the remaining (n-1) x (n-1) matrix is the number of spanning trees of the graph.

The proof is a clever use of the Cauchy-Binet formula, but you can trust it and test it. Compute the determinant exactly with Fraction arithmetic and Gaussian elimination so no rounding error creeps in. The graph must be connected, otherwise the determinant is 0, which is correct: no spanning tree exists.

Python Counting spanning trees with Kirchhoff's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A triangle has 3 spanning trees (drop any one edge), a square has 4, the "house" (a square with a roof) has 11, the K4 graph has 16, and the determinant agrees with the brute force that tries every (n-1)-edge subset. Brute force checks C(E, n-1) subsets and becomes hopeless quickly, while the determinant takes O(n^3).

Cayley's formula

For the complete graph K_n every pair of vertices is joined, and the number of spanning trees is

TEXT
n^(n-2)

That is also the number of labelled trees on n vertices. For n = 4 it is 16, which matches the K4 line above. Feed K_n to Kirchhoff and the determinant collapses to this closed form, but the neatest proof is a bijection with sequences.

Prufer sequences

A Prufer sequence encodes a labelled tree on vertices 1..n as a list of n - 2 numbers, each between 1 and n. There are n^(n-2) such lists, which is exactly Cayley's count, so the encoding must be one-to-one. The encoding is simple:

  1. Find the smallest leaf (the vertex of degree 1 with the smallest label).
  2. Append its neighbour to the sequence and remove the leaf.
  3. Repeat until two vertices remain.

To decode, a vertex with label v appears in the sequence exactly degree(v) - 1 times. Rebuild by repeatedly taking the smallest vertex that does not appear in the remaining sequence, joining it to the next sequence element.

Python Prufer encode and decode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The code of the sample tree is [4, 4, 4, 5, 5]: vertex 4 has degree 4 and appears 4 - 1 = 3 times, vertex 5 has degree 3 and appears twice, and the leaves never appear. A star on six vertices gives [3, 3, 3, 3] and a path gives [2, 3, 4, 5]. All 125 sequences for n = 5 decode to 125 different trees, which is Cayley's 5^3 and a direct check that the encoding is a bijection. Prufer codes are also handy for generating a uniformly random labelled tree: pick a random sequence and decode it.

Reverse-delete: a third MST algorithm

You know Kruskal (add the cheapest edge that creates no cycle) and Prim (grow one tree). Reverse-delete runs Kruskal backwards: start with all edges and consider them from the heaviest to the lightest. Delete an edge if the graph stays connected without it; keep it otherwise (it is a bridge in the current graph). What remains is a minimum spanning tree.

Why correct? An edge is the heaviest on some cycle exactly when you can delete it, and by the cycle property the heaviest edge of any cycle is never needed in a minimum spanning tree.

Python Reverse-delete against Kruskal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both algorithms return a tree of the same total weight (they may choose different edges when weights tie). Reverse-delete is slow in this form: each deletion test is a connectivity check, giving O(E (V + E)). With the dynamic connectivity structure of Holm, de Lichtenberg and Thorup it drops to O(E log V (log log V)^3), but it is mostly studied for its elegance, not used in practice.

Common mistakes

  • Not dropping a row and a column. The full Laplacian has determinant 0 for every graph; the theorem needs a cofactor.
  • Floating-point determinants. For large graphs the result is huge and rounding ruins it; use Fraction, or a modular determinant mod a prime.
  • Forgetting parallel edges. In a multigraph, L[i][j] is -k for k parallel edges, and each edge counts as a separate tree choice.
  • Mixing up labelled and unlabelled trees. Cayley's n^(n-2) counts labelled trees: two relabellings of the same shape count twice.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Kirchhoff's theorem compute?

    Any (n-1) x (n-1) minor of the Laplacian matrix has determinant equal to the number of spanning trees.
  2. 2. How many labelled trees exist on 6 vertices?

    Cayley's formula gives n^(n-2) = 6^4 = 1296.
  3. 3. How many entries does the Prufer sequence of a tree on n vertices have?

    You remove leaves until two vertices remain, which takes n - 2 steps, and each step records one neighbour.
  4. 4. In reverse-delete, when is an edge removed?

    Edges are tried from heaviest to lightest; if the graph stays connected, the edge was the heaviest on some cycle and is not needed.

Summary

  • The Laplacian matrix has degrees on the diagonal and -1 for edges; any cofactor's determinant counts spanning trees.
  • Cayley's formula: the complete graph on n vertices has n^(n-2) spanning trees.
  • A Prufer sequence of n-2 labels is a one-to-one code for a labelled tree and gives random trees for free.
  • Reverse-delete drops edges from heaviest to lightest while the graph stays connected, producing an MST.

Next: Eulerian and Hamiltonian Paths, where we add Fleury's algorithm and the Chinese postman problem.