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)
“But, where the road runs near the stream,
Oft through the trees they catch a glance
Of passing troops in the sun’s beam—
Pennon, and plume, and flashing lance!
Forth to the world those soldiers fare,
To life, to cities, and to war!”
—Matthew Arnold (1822–1888)