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:
“Love is sinister,
is mean to us in separation;
makes our thin bodies thinner.
This fellow Death
lacks mercy
and is good at counting our days.
And Master,
you, too, are subject
to the plague of jealousy
so think:
how could womenfolk,
soft as sprouts,
live like this?”
—Amaru (c. seventh century A.D.)
“Who shall describe the inexpressable tenderness and immortal life of the grim forest, where Nature, though it be midwinter, is ever in her spring, where the moss-grown and decaying trees are not old, but seem to enjoy a perpetual youth.”
—Henry David Thoreau (1817–1862)