Prüfer Codes of Labeled Trees

nodes

9

pick a tree

1000000

{2,8,9,4,7,7,2}

In 1889, Cayley proved that there are

n-2

n

labeled trees on

n

nodes. In 1918, Prüfer found a method for constructing each tree.

Consider the tree with code {2, 8, 9, 4, 7, 7, 2} that is given as the default tree in this Demonstration. The first digit of the Prüfer code is the branch that has the smallest isolated number. Pruning that branch gives a new tree, and the process repeats, as shown in the Details.