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.
Read more about this topic: Spanning Tree
Famous quotes containing the words counting and/or trees:
“But counting up to two
Is harder to do....”
—Philip Larkin (1922–1986)
“Bright yellow, red, and orange,
The leaves come down in hosts;
The trees are Indian princes,
But soon they’ll turn to ghosts;”
—William Allingham (1824–1889)