Spanning Tree - Counting Spanning Trees

Counting Spanning Trees

The number t(G) of spanning trees of a connected graph is a well-studied invariant. In some cases, it is easy to calculate t(G) directly. For example, if G is itself a tree, then t(G)=1, while if G is the cycle graph with n vertices, then t(G)=n. For any graph G, the number t(G) can be calculated using Kirchhoff's matrix-tree theorem (follow the link for an explicit example using the theorem).

Cayley's formula is a formula for the number of spanning trees in the complete graph with n vertices. The formula states that . Another way of stating Cayley's formula is that there are exactly labelled trees with n vertices. Cayley's formula can be proved using Kirchhoff's matrix-tree theorem or via the Prüfer code.

If G is the complete bipartite graph, then, while if G is the n-dimensional hypercube graph, then . These formulae are also consequences of the matrix-tree theorem.

If G is a multigraph and e is an edge of G, then the number t(G) of spanning trees of G satisfies the deletion-contraction recurrence t(G)=t(G-e)+t(G/e), where G-e is the multigraph obtained by deleting e and G/e is the contraction of G by e, where multiple edges arising from this contraction are not deleted.