How to Learn Prüfer Sequences: Leaf Removal, Tree Codes, Decoding, Degree Counts and Cayley’s Formula

Wait, What?

Every labelled tree on n vertices can be compressed into exactly n−2 labels—and decoded back without ambiguity.

A Prüfer sequence is one of the cleanest bridges between graph algorithms and combinatorics. It converts a labelled tree into a sequence by repeatedly removing the smallest-labelled leaf and recording its neighbour. The process looks almost mechanical, yet it creates a bijection between labelled trees and sequences. That bijection gives an elegant proof of Cayley’s formula, supports random labelled-tree generation, and provides a compact way to reason about vertex degrees.

The algorithm is especially useful educationally because learners can understand the basic procedure quickly, then uncover progressively deeper invariants.

Quick Answer

Learn Prüfer sequences through tree and leaf basics → encoding by leaf removal → decoding from occurrence counts → degree invariant → bijection → Cayley’s formula → efficient data structures → random-tree generation → validation and edge cases. The beginner task is to encode and decode small trees correctly. The professional task is to exploit the bijection while preserving label conventions, complexity guarantees and uniform sampling.

1. Start with the object: a labelled tree

A tree is a connected undirected graph with no cycles. A labelled tree has distinct labels on its vertices. Prüfer coding depends on those labels because the standard encoding rule repeatedly chooses the smallest-labelled leaf.

A leaf is a vertex of degree 1. Every finite tree with at least two vertices has at least two leaves. That fact guarantees the encoding process always has a leaf available until only two vertices remain.

2. The encoding rule

Given a labelled tree with n vertices:

1. Find the smallest-labelled leaf.
2. Record the label of its unique neighbour.
3. Delete the leaf and its incident edge.
4. Repeat until only two vertices remain.

The recorded list has length n−2. That list is the Prüfer sequence.

3. Encode one tree by hand

Consider the labelled tree with edges:

1—4
2—4
3—4
4—5
5—6

The initial leaves are 1, 2, 3 and 6. The smallest is 1, whose neighbour is 4, so record 4 and remove 1.

Now the smallest leaf is 2. Record 4 and remove 2.

Then remove leaf 3 and record 4.

After that, vertex 4 becomes a leaf connected to 5. Record 5 and remove 4.

Two vertices remain, 5 and 6, so stop.

Prüfer sequence = [4, 4, 4, 5]

The original tree had six vertices, and the sequence length is 6−2=4.

4. The degree invariant

This is the first deep fact to learn:

degree(v) = 1 + number of times v appears in the Prüfer sequence

Why? Every time v is recorded, one adjacent leaf is removed while v remains in the tree. Eventually v itself becomes a leaf and disappears without being recorded again. Therefore each recorded occurrence accounts for one incident edge beyond the final leaf edge.

In the example [4,4,4,5], vertex 4 appears three times, so degree(4)=4. Vertex 5 appears once, so degree(5)=2. Vertices 1,2,3 and 6 never appear, so each has degree 1.

This gives an immediate check on both encoding and decoding.

5. Decoding: reconstruct the tree from the sequence

Suppose the sequence has length n−2. The vertex labels are known, often 1…n or 0…n−1 depending on the convention.

For each vertex v, initialise:

degree[v] = 1 + occurrences of v in the sequence

Then process the sequence from left to right. At each step:

1. Choose the smallest vertex with degree 1.
2. Connect that leaf to the current sequence value x.
3. Decrease degree[leaf] and degree[x].
4. Continue to the next sequence value.

After the sequence is exhausted, exactly two degree-1 vertices remain. Connect them.

6. Decode the example

Start with [4,4,4,5] on labels 1…6.

Occurrence counts give degrees:

1:1  2:1  3:1  4:4  5:2  6:1

Read the first 4. The smallest degree-1 vertex is 1, so add edge 1—4. Reduce degrees.

Read the second 4. The smallest leaf is now 2, so add 2—4.

Read the third 4. Add 3—4.

Read 5. After removing the first three leaves, vertex 4 has become degree 1, so add 4—5.

The remaining leaves are 5 and 6, so add 5—6. The original tree is recovered exactly.

7. Why the mapping is a bijection

Every labelled tree produces one deterministic Prüfer sequence under the smallest-leaf rule. Conversely, every valid sequence of length n−2 over the n labels decodes to exactly one labelled tree.

That gives a one-to-one correspondence:

labelled trees on n vertices  ↔  sequences of length n−2 over n labels

This bijection is the heart of the theory. Encoding and decoding are not merely compression tricks; they show that the two sets have exactly the same size.

8. Cayley’s formula falls out immediately

How many sequences of length n−2 can be formed using n possible labels? Each position has n choices, so there are:

n^(n−2)

Because Prüfer sequences are in bijection with labelled trees, the number of labelled trees on n vertices is also:

n^(n−2)

This is Cayley’s formula.

The algorithm therefore acts as a counting proof. Instead of directly counting tree shapes, it translates trees into an easier object to count.

9. Naive implementation versus efficient implementation

A naive encoder can repeatedly scan all vertices to find the smallest leaf. That is easy to understand but may cost O(n²).

A standard efficient implementation maintains leaf candidates in a min-priority queue. Each vertex enters the queue when its degree falls to 1. Each insertion or removal costs O(log n), yielding a simple O(n log n) implementation.

More specialised algorithms can achieve O(n) time under suitable label assumptions. Current NetworkX 3.6.1 documentation reports linear-time implementations for converting to and from Prüfer sequences.

10. Conceptual encoding pseudocode

degree[v] = number of neighbors of v
leaves = min-priority-queue of all v with degree[v] == 1
sequence = []

repeat n - 2 times:
    leaf = extract_min(leaves)
    neighbor = the unique active neighbor of leaf
    append neighbor to sequence

    remove edge leaf—neighbor
    degree[leaf] -= 1
    degree[neighbor] -= 1

    if degree[neighbor] == 1:
        insert neighbor into leaves

return sequence

The phrase “unique active neighbour” matters. If you physically delete edges, adjacency updates are straightforward. If you keep the original adjacency lists, you need an efficient way to skip neighbours that have already been removed.

11. Conceptual decoding pseudocode

degree[v] = 1 for all vertices

for x in sequence:
    degree[x] += 1

leaves = min-priority-queue of all v with degree[v] == 1
edges = []

for x in sequence:
    leaf = extract_min(leaves)
    add edge leaf—x to edges

    degree[leaf] -= 1
    degree[x] -= 1

    if degree[x] == 1:
        insert x into leaves

u = extract_min(leaves)
v = extract_min(leaves)
add edge u—v

return edges

12. Label conventions can break otherwise correct code

Some textbooks use labels 1…n. Many software libraries use 0…n−1. Current NetworkX Prüfer functions expect the latter convention.

If your sequence is [4,4,4,5] under labels 1…6, you cannot pass it unchanged to a function that assumes 0…5. Relabel first or use a compatible implementation.

This is not a mathematical problem; it is an interface contract.

13. Random labelled trees

The bijection gives a simple method for uniform random labelled-tree generation:

1. Generate a uniformly random sequence of length n−2, with each entry chosen uniformly from the n labels.
2. Decode the sequence into a tree.

Because every labelled tree corresponds to exactly one sequence, uniform sampling of sequences produces uniform sampling of labelled trees.

This is different from generating a random graph and conditioning on it being a tree, and different from random spanning-tree sampling on a fixed host graph.

14. Degree-constrained counting

The occurrence-count invariant makes Prüfer sequences useful in combinatorial counting. If you prescribe degrees d₁,…,dₙ satisfying the tree degree sum 2(n−1), then vertex i must appear exactly dᵢ−1 times in the sequence.

The number of labelled trees with that exact degree sequence becomes a multinomial count:

(n−2)! / Π_i (d_i−1)!

This is an advanced but beautiful example of an algorithmic representation turning a graph-counting problem into a sequence-counting problem.

15. What Prüfer sequences do not preserve transparently

A Prüfer sequence contains complete information about the labelled tree, but some properties are not visually obvious from the sequence. Graph diameter, centre, depth from a chosen root and subtree shapes may require decoding or additional reasoning.

Compression does not mean every query becomes easier.

16. How to teach Prüfer sequences from beginner to professional

This topic fits a progressive programming pedagogy particularly well.

• Predict: identify the smallest leaf and predict the next emitted label.
• Run: compare with a reference encoder.
• Investigate: track degrees after every removal.
• Modify: move one edge while keeping a tree and predict which sequence positions change.
• Make: implement both encoder and decoder, then prove round-trip correctness empirically.

For beginners, a faded Parsons task can supply the priority-queue skeleton while leaving only the degree-update lines missing. This separates the algorithmic invariant from syntax load.

17. Round-trip tests are the natural validation tool

Encoding and decoding are inverses, so test:

decode(encode(tree)) == tree
encode(decode(sequence)) == sequence

Use many random cases. For trees, compare edge sets after normalising unordered edge endpoints. For sequences, equality is direct.

Also test the degree invariant independently: count occurrences in the sequence and compare with tree degrees.

18. Common failure states

• Removing an arbitrary leaf instead of the smallest-labelled leaf.
• Continuing until one vertex remains instead of stopping at two.
• Forgetting that the sequence length must be n−2.
• Using the wrong label range.
• Updating the neighbour’s degree but not inserting it when it becomes a leaf.
• Decoding with degree equal to occurrence count instead of occurrence count plus one.
• Calling uniformly random sequences “random spanning trees” without stating that the sampling space is all labelled trees on the complete label set.

19. Complexity and professional engineering

A priority-queue implementation is simple, transparent and usually sufficient. For very large n, heap overhead and memory layout matter. If labels are dense integers, specialised linear-time methods can exploit ordering more aggressively.

Professional implementations should state:

• label convention;
• accepted input type;
• time and memory complexity;
• whether the tree is validated before encoding;
• behaviour for n=0, n=1 and n=2;
• whether random-tree generation is statistically uniform.

20. Practice ladder

• Beginner: encode three small labelled trees by hand.
• Foundation: decode three sequences and verify the degree invariant.
• Intermediate: implement heap-based encoding and decoding.
• Advanced: derive Cayley’s formula and the degree-sequence counting formula.
• Professional: build a uniform random labelled-tree generator, run statistical checks on degree frequencies, and compare your round-trip results with NetworkX.

21. Ownership boundary

This article owns Prüfer encoding and decoding for labelled trees, including the degree invariant, Cayley’s formula and uniform random labelled-tree generation. It does not replace minimum spanning trees, random spanning trees of a fixed graph, tree traversal, tree decomposition or general graph compression.

Sources and further reading

• NetworkX 3.6.1 documentation: to_prufer_sequence and from_prufer_sequence.
• NetworkX documents the bijection between labelled trees and Prüfer sequences and current linear-time implementations.
• Xiaodong Wang, Lei Wang and Yingjie Wu, “An optimal algorithm for Prufer codes,” Journal of Software Engineering and Applications, 2009, DOI: 10.4236/jsea.2009.22016.
• Current programming-education work on PRIMM and Parsons problems supports progressing from prediction and code reading toward modification and independent construction.

Professional rule: you understand Prüfer sequences when you can move freely between tree, sequence, degree counts and counting arguments—and can explain exactly why the encoding and decoding procedures are inverses.