Cayley Formula and Matrix-Tree Theorem

Counting spanning trees reveals deep connections between combinatorics, linear algebra, and graph structure. Two fundamental results—Cayley's formula and the matrix-tree theorem—provide powerful tools for enumeration.

TheoremCayley's Formula

The complete graph $K_n$ has exactly $n^{n-2}$ labeled spanning trees.

For example: $K_3$ has $3^1 = 3$ trees, $K_4$ has $4^2 = 16$ trees, and $K_5$ has $5^3 = 125$ trees.

Multiple proofs of Cayley's formula exist, each offering different insights. The Prüfer code provides a bijection between labeled trees on $n$ vertices and sequences of length $n-2$ from $\{1, 2, \ldots, n\}$ , directly establishing the count.

DefinitionPrüfer Code

The Prüfer code of a labeled tree $T$ on vertices $\{1, 2, \ldots, n\}$ is constructed by:

Find the leaf with smallest label, say $v$
Record the label of $v$ 's unique neighbor
Remove $v$ and repeat until 2 vertices remain

This produces a sequence $(a_1, a_2, \ldots, a_{n-2})$ with each $a_i \in \{1, \ldots, n\}$ . The map is bijective, proving Cayley's formula.

ExamplePrüfer Code Construction

For a tree with edges $\{(1,3), (2,3), (3,4), (4,5)\}$ on 5 vertices:

Leaf 1 connects to 3: record $a_1 = 3$ , remove vertex 1
Leaf 2 connects to 3: record $a_2 = 3$ , remove vertex 2
Leaf 3 connects to 4: record $a_3 = 4$ , remove vertex 3
Two vertices remain, stop

Prüfer code: $(3, 3, 4)$ . Since there are $5^3 = 125$ such codes, $K_5$ has 125 spanning trees.

TheoremMatrix-Tree Theorem (Kirchhoff)

For any graph $G$ with Laplacian matrix $L$ , let $L_{ij}$ denote the matrix obtained by deleting row $i$ and column $j$ from $L$ . Then the number of spanning trees of $G$ is: $\tau(G) = \det(L_{ii})$

for any $i$ . Remarkably, this determinant is independent of which row and column are deleted.

The matrix-tree theorem provides an algebraic method to count spanning trees without enumeration, connecting graph structure to linear algebra through the Laplacian matrix.

ExampleMatrix-Tree for $K_4$

For $K_4$ , the Laplacian is: $L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix}$

Deleting the first row and column: $L_{11} = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{pmatrix}$

Computing: $\det(L_{11}) = 16$ , confirming Cayley's formula: $4^{4-2} = 16$ .

Remark

The matrix-tree theorem extends to weighted graphs by replacing $-1$ entries with $-w_{ij}$ (negative edge weights) in the Laplacian. The determinant then sums over all spanning trees weighted by the product of their edge weights, providing a generating function for weighted tree counting.

These counting results have applications in network reliability, random graph generation, and statistical physics (counting configurations in the Ising model), demonstrating the interplay between combinatorics and analysis in graph theory.