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:
“If you’re counting my eyebrows, I can help you. There are two.”
—Billy Wilder (b. 1906)
“At the heart of all beauty lies something inhuman, and these hills, the softness of the sky, the outline of these trees at this very minute lose the illusory meaning with which we had clothed them, henceforth more remote than a lost paradise ... that denseness and that strangeness of the world is absurd.”
—Albert Camus (1913–1960)