Prüfer sequence

From Wikipedia, the free encyclopedia

In combinatorial mathematics, the Prüfer sequence (or Prüfer code) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.

1 Algorithm
2 Example
3 Cayley's formula
4 Other applications
5 References
6 External links

[edit] Algorithm

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 {1, 2, ..., n}. 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 sequence of a labeled tree is clearly unique and has length n − 2.

[edit] Example

A labeled tree with Prüfer sequence 4445.

Consider the above algorithm run on the simple example 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 4445.

[edit] 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 — this much is clear. Somewhat less obvious is the fact that 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. This can be proved fairly easily by induction on n.

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 size nⁿ⁻², so the existence of this bijection proves Cayley's formula, i.e. that there are nⁿ⁻² labeled trees on n vertices.

[edit] Other applications

Cayley's formula can be strengthened to prove the following claim:

The number of spanning trees in a complete graph $K n$ with degrees $d_1, d_2, \ldots, d_n$ is equal to

$\frac{(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots(d_{n}-1)!}.$

The proof follows by observing that in the Prüfer sequence number $i$ appears exactly $(d i - 1)$ times.

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 n₁ in one partition and vertices n₁ + 1 to n in the other partition, the number of labeled spanning trees of G is $n_{1}^{n_2-1} n_{2}^{n_1-1}$ , where n₂ = n − n₁.