Prüfer Labeled Tree Codes

A Prüfer sequence is a unique sequence of integers associated with a labeled tree. For a tree with n vertices labeled 0 to n-1, the sequence has length n-2. This establishes a bijection between labeled trees and length n-2 sequences.

Worked Example

Consider the Prüfer sequence `[3, 3, 1]` for n=5 vertices.

Initialize degrees: The sequence `[3, 3, 1]` implies vertices 3 and 1 appear. The degree of vertex v is 1 + the number of times it appears in the sequence. So the degrees are `1, 2, 1, 3, 1`.
Find the smallest available vertex of degree 1. It is 0. Connect it to the first element in the sequence, 3. Edge: `0-3`. Decrease degrees of both.
Next sequence element is 3. The smallest degree 1 vertex is now 2. Edge: `2-3`. Decrease degrees.
Next sequence element is 1. The smallest degree 1 vertex is now 3 (its degree decreased from 3 to 1). Edge: `1-3`. Decrease degrees.
Sequence is empty. The remaining degree 1 vertices are 1 and 4. Edge: `1-4`.

The resulting tree has edges `0-3; 1-3; 1-4; 2-3`.

Result Edges: 0-3; 1-3; 1-4; 2-3

Experiment

Explore the presets using the interactive module:

Select the Interactive Module and choose the "Path five" preset.
Observe the computed degree array: `1, 2, 2, 2, 1` which is typical for a path graph.
Select the "Star five" preset and notice that the center node has a high degree while all others are leaves with degree 1.
Check the boundary cases such as "Pair", which has an empty Prüfer sequence.

Limitations

The algorithm is restricted to trees with n ≥ 2 vertices, as the sequence length is n-2. It does not naturally extend to disconnected graphs (forests) or n ≤ 1 without special conventions outside the standard definition.

References

NetworkX: from_prufer_sequence. A widely used library implementation that documents the standard algorithm for constructing a tree from a Prüfer sequence.

Prüfer Labeled Tree Codes