Spanning tree count τ(G): number of spanning trees. Kirchhoff's matrix tree theorem (1847): τ = any cofactor of L(G) = product of non-zero Laplacian eigenvalues / n. Cayley's formula: τ(K_n) = n^{n-2}.
How to Use
Select graph:
- τ(G): Tree count
- Formula: Closed form
- Cayley: K_n = n^{n-2}
Matrix Tree Theorem
Form Laplacian L = D - A (degree matrix minus adjacency). Delete any row i and column i. τ(G) = det of resulting (n-1)×(n-1) matrix. Equivalently: τ = (λ₁·λ₂·...·λ_{n-1})/n where λᵢ are non-zero eigenvalues of L.
Cayley's Formula
τ(K_n) = n^{n-2}. For n=4: 4²=16 spanning trees. Proved by Cayley (1889). Also proved via Prüfer sequences: bijection between labeled trees on n vertices and sequences of length n-2 from {1,...,n}.
Step-by-Step Instructions
- 1Select graph.
- 2Compute τ(G).
- 3See formula.
- 4Check Cayley.
- 5Compare graphs.