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:
“What we commonly call man, the eating, drinking, planting, counting man, does not, as we know him, represent himself, but misrepresents himself. Him we do not respect, but the soul, whose organ he is, would he let it appear through his action, would make our knees bend.”
—Ralph Waldo Emerson (1803–1882)
“One wonders that the tithing-men and fathers of the town are not out to see what the trees mean by their high colors and exuberance of spirits, fearing that some mischief is brewing. I do not see what the Puritans did at this season, when the maples blaze out in scarlet. They certainly could not have worshiped in groves then. Perhaps that is what they built meeting-houses and fenced them round with horse-sheds for.”
—Henry David Thoreau (1817–1862)