Spanning Tree Count (Cayley & Matrix-Tree)

Cayley's formula and the Matrix-Tree Theorem count spanning trees.

The idea

A tree is a connected graph containing no cycle. A spanning tree of a connected graph $G$ is a subgraph that is a tree and includes every vertex of $G$: a minimal set of edges holding all of $G$ together. A graph normally has many spanning trees, and $\tau(G)$ denotes how many. Two classical theorems count them.

Theorem (Cayley's formula).

The complete graph $K_{n}$, on $n$ labeled vertices with every pair joined, has $\tau(K_{n}) = n^{n-2}$ spanning trees. Equivalently, there are $n^{n-2}$ distinct trees on $n$ labeled vertices.

For any graph $G$, let $D$ be the degree matrix (diagonal, carrying each vertex's degree) and $A$ the adjacency matrix (a $1$ in position $(i, j)$ when vertices $i$ and $j$ are joined, and $0$ otherwise), and set $L = D - A$, the Laplacian.

Theorem (Matrix-Tree Theorem).

For any graph $G$ with Laplacian $L$, delete any one row of $L$ together with the column of the same index. The determinant of what remains equals $\tau(G)$, whichever row and column were deleted.

A graph has exponentially many subgraphs, so counting spanning trees by listing them is hopeless; each theorem replaces the entire search with a single evaluation.

Ways to work on it

• Walkthrough. Count spanning trees — a closed formula for complete graphs, a determinant for the rest.
• Practice. Count spanning trees of a complete graph with Cayley.
• Hardest. Count a graph's spanning trees with the Matrix-Tree determinant.

Not sure where to start? Take the ten-question placement test.