number of unrooted labeled trees


Theorem 1.

(Cayley) The number of [isomorphism classes of] labeled treesMathworldPlanetmath on n vertices [n]={1,2,,n} is nn-2.

This is sequence A000272 in the http://www.research.att.com/ njas/sequencesOnline Encyclopedia of Integer Sequences

For n=1 and n=2 the result is obvious. For n=3, the possible trees are

                  

while for n=4, the 42=16 trees fall into two groups: 12 trees with linear structure and 4 with a star structure. There are 12 linear trees since there are 24 orderings of 1,2,3,4 and mirror orderings give the same tree; there are 4 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 [n] is nn-2.

A Prüfer code on [n] is a sequence of n-2 elements a1,a2,,an-2 chosen from [n] (repetitions are allowed). Obviously there are nn-2 codes on n symbols.

Given a tree T on [n] with n3, convert it to a Prüfer code using the following algorithm:


for j=1 to n-2
      let lj be the vertex in T with the smallest label
      let aj be the vertex adjacentPlanetmathPlanetmathPlanetmath to lj
      remove lj from T
  next j

When this process completesPlanetmathPlanetmath, the result will be a Prüfer code (of length n-2) on n symbols; this mapping is clearly well-defined.

Let’s walk through a more complicated example. Consider the following tree on 8 vertices:

    ??      

Using the algorithm above, we get

lj aj
4 1
5 1
6 3
3 1
1 2
7 2

and thus the Prüfer code associated with this tree is 1,1,3,1,2,2.

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 T on [n] given a Prüfer code on n 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 n3 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 aj.

To see that every non-leaf must appear in the list, note that each vertex was either removed as one of the lj or it remains in the two-vertex tree at the end of the process. In either event, one of its adjacent verticesMathworldPlanetmath 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 a1. The leaf that was removed (l1) must be the smallest leaf vertex, which is the smallest number not appearing in the code. It must attach to a1. Essentially, this process continues as one moves forward through the aj, 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:


A the set of leaf vertices
  T the connected tree on the two vertices an-2 and the highest-numbered leaf
  for j=1 to n-2
      add aj and the lowest-numbered node l in A to T (if not already in T)
      add an edge in T between aj and l
      remove l from A
      if akaj for any k>j, add aj to A
  next j

Let’s see how this process works on the Prüfer code above.

We start by letting T be the tree on the two vertices 2 and 8 with an edge between them:

The initial value for A (the available vertices) is 4,5,6,7.

a1=1, so add 1,4, and an edge between 1 and 4 to T. 1 appears later in A, so we do not add it to A.

a2=1 and A={5,6,7}, so add 5 and an edge between 1 and 5:

??

a3=3 and A={6,7}. Add 3,6 and an edge from 3 to 6. This is the last occurrence of 3 in the code, so add 3 to A.

??   

a4=1 and A={3,7}. Add an edge from 1 to 3. Add 1 to A.

??   

a5=2 and A={1,7}. Add an edge from 1 to 2.

    ??   

a6=2 and A={7}. Add 7 and an edge from 2 to 7.

    ??      

We have reconstructed the original tree.

Title number of unrooted labeled trees
Canonical name NumberOfUnrootedLabeledTrees
Date of creation 2013-03-22 17:31:20
Last modified on 2013-03-22 17:31:20
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 6
Author rm50 (10146)
Entry type Theorem
Classification msc 05C30
Defines Prufer code
Defines Prüfer code