number of unrooted labeled trees
(Cayley) The number of [isomorphism classes of] labeled trees on vertices is .
This is sequence A000272 in the http://www.research.att.com/ njas/sequencesOnline Encyclopedia of Integer Sequences
For and the result is obvious. For , the possible trees are
while for , the trees fall into two groups: trees with linear structure and with a star structure. There are linear trees since there are orderings of and mirror orderings give the same tree; there are star trees since the tree is determined by its central element.
There are many proofs of this theorem; the demonstration we give uses the Prüfer bijection, which associates with each such tree its Prüfer code; it is easily seen that the number of Prüfer codes on is .
A Prüfer code on is a sequence of elements chosen from (repetitions are allowed). Obviously there are codes on symbols.
Given a tree on with , convert it to a Prüfer code using the following algorithm:
let be the vertex in with the smallest label
let be the vertex adjacent to
Let’s walk through a more complicated example. Consider the following tree on vertices:
Using the algorithm above, we get
and thus the Prüfer code associated with this tree is .
The easiest way to see that this map is a bijection is by explicitly constructing its inverse. To do this, we must show how to construct a tree on given a Prüfer code on symbols.
Note first that the code for a given tree contains only the non-leaf vertices, and that each non-leaf vertex appears at least once in the code. The first of these statements is obvious from the algorithm - given that and since the algorithm stops when there are only two vertices left in the tree, no leaf vertex in the original tree can be selected as an .
To see that every non-leaf must appear in the list, note that each vertex was either removed as one of the or it remains in the two-vertex tree at the end of the process. In either event, one of its adjacent vertices was removed from the tree at some point, so the vertex would appear in the code. In fact, it is clear that the number of times each vertex appears in the code is one less than its degree in the tree.
Given this, it’s rather straightforward to reconstruct the tree. Consider . The leaf that was removed () must be the smallest leaf vertex, which is the smallest number not appearing in the code. It must attach to . Essentially, this process continues as one moves forward through the , except that allowances must be made for non-leaf vertices that are removed at later steps as they become leaf vertices. Here is an algorithm to reconstruct a tree from a Prüfer code:
the set of leaf vertices
the connected tree on the two vertices and the highest-numbered leaf
add and the lowest-numbered node in to (if not already in )
add an edge in between and
if for any , add to
Let’s see how this process works on the Prüfer code above.
We start by letting be the tree on the two vertices and with an edge between them:
The initial value for (the available vertices) is .
, so add , and an edge between and to . appears later in , so we do not add it to .
and , so add and an edge between and :
and . Add and an edge from to . This is the last occurrence of in the code, so add to .
and . Add an edge from to . Add to .
and . Add an edge from to .
and . Add and an edge from to .
We have reconstructed the original tree.
|Title||number of unrooted labeled trees|
|Date of creation||2013-03-22 17:31:20|
|Last modified on||2013-03-22 17:31:20|
|Last modified by||rm50 (10146)|