How to find the Prüfer code of a tree quickly

Key concept: Prüfer codes are one of those topics where the algorithm matters more than the intuition at first. Once you know the leaf-removal rule, the code comes out systematically.

Step by step

To find the Prüfer code of a tree, repeat this rule until only two vertices remain:

1. Remove the smallest-numbered leaf.
2. Record its neighbor.

The list of recorded neighbors is the Prüfer code.

Since the prompt says the answer should be just the code and no explanation, the key thing is to follow the leaf-removal order exactly. If the tree has $n$ vertices, the Prüfer code will have length $n-2$.

If you want, I can also format the code as a plain list once the tree image or edge list is provided.

Pitfall alert

The biggest trap is removing any leaf instead of the smallest leaf. Prüfer coding is not arbitrary; the smallest labeled leaf must be chosen each time. Another easy error is recording the removed leaf itself instead of its neighbor.

Try different conditions

If the tree labels are changed, the Prüfer code changes too, even if the shape stays the same. For example, relabeling the vertices can completely alter the sequence because the algorithm depends on numeric order.

Further reading

leaf-removal algorithm, tree encoding, Cayley Prüfer sequence