Algorithm to convert a tree into a Prüfer sequence
One can generate a labeled tree's Prüfer sequence by iteratively removing vertices from the tree until only two vertices remain. Specifically, consider a labeled tree T with vertices. At step i, remove the leaf with the smallest label and set the ith element of the Prüfer sequence to be the label of this leaf's neighbour. The Prüfer sequence of a labeled tree is unique and has length n − 2.
Example
Consider the above algorithm run on the tree shown to the right. Initially, vertex 1 is the leaf with the smallest label, so it is removed first and 4 is put in the Prüfer sequence. Vertices 2 and 3 are removed next, so 4 is added twice more. Vertex 4 is now a leaf and has the smallest label, so it is removed and we append 5 to the sequence. We are left with only two vertices, so we stop. The tree's sequence is.
Algorithm to convert a Prüfer sequence into a tree
Let be a Prüfer sequence: The tree will have n+2 nodes, numbered from 1 to n+2. For each node set its degree to the number of times it appears in the sequence plus 1. For instance, in pseudo-code: Convert-Prüfer-to-Tree 1 n ← length 2 T ← a graph with n + 2 isolated nodes, numbered 1 ton + 2 3 degree ← an array of integers 4 for each node i in Tdo 5 degree ← 1 6 for each value i in ado 7 degree ← degree + 1 Next, for each number in the sequence a, find the first node, j, with degree equal to 1, add the edge to the tree, and decrement the degrees of j and a. In pseudo-code: 8 for each value i in ado 9 for each node j in Tdo 10 ifdegree = 1 then 11 Insert edge into T 12 degree ← degree - 1 13 degree ← degree - 1 14 break At the end of this loop two nodes with degree 1 will remain. Lastly, add the edge to the tree. 15 u ← v ← 0 16 for each node i in T 17 ifdegree = 1 then 18 ifu = 0 then 19 u ← i 20 else 21 v ← i 22 break 23 Insert edge into T 24 degree ← degree - 1 25 degree ← degree - 1 26 returnT
Cayley's formula
The Prüfer sequence of a labeled tree on n vertices is a unique sequence of length n − 2 on the labels 1 to n. For a given sequence S of length n-2 on the labels 1 to n, there is a unique labeled tree whose Prüfer sequence is S. The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on n vertices and the set of sequences of length n − 2 on the labels 1 to n. The latter set has sizenn−2, so the existence of this bijection proves Cayley's formula, i.e. that there are nn−2 labeled trees on n vertices.
Cayley's formula can be strengthened to prove the following claim:
Cayley's formula can be generalized: a labeled tree is in fact a spanning tree of the labeled complete graph. By placing restrictions on the enumerated Prüfer sequences, similar methods can give the number of spanning trees of a complete bipartite graph. If G is the complete bipartite graph with vertices 1 to n1 in one partition and vertices n1 + 1 to n in the other partition, the number of labeled spanning trees of G is, where n2 = n − n1.
Generating uniformly distributed random Prüfer sequences and converting them into the corresponding trees is a straightforward method of generating uniformly distributed random labelled trees.
