Why Prüfer Encoding Is A Bijection

Two Procedures, One Correspondence

Prüfer encoding turns a labeled tree into a short sequence of labels: repeatedly remove the smallest-labeled leaf and record its neighbor. Decoding starts with a sequence and repeatedly attaches the smallest label missing from the current sequence to its first entry. The key to proving these procedures are inverse is to track both objects that change during decoding: the remaining labels and the remaining sequence.

Throughout, a tree is a finite, connected, simple graph with no cycles. Fix an integer \(n\ge2\), and use the labels \([n]=\{1,2,\ldots,n\}\). A Prüfer sequence on \([n]\) has length \(n-2\), and each of its entries belongs to \([n]\). The case \(n=2\) has one labeled tree and one sequence, the empty sequence.

These rules are well-defined. A tree with at least two vertices has a leaf: for example, an endpoint of a longest path must be a leaf, since another neighbor would either extend the path or create a cycle. Thus the encoding can choose a leaf at every required step. In decoding, if \(r\ge3\) labels remain, the current sequence has length \(r-2\). It can contain at most \(r-2\) distinct labels, so at least two current labels are absent. Its first entry is a current label and is present in the sequence, so it cannot be the chosen missing label.

Before proving that the procedures undo each other, we establish the connection between missing labels and leaves. For a sequence over a current label set, “missing” means that the label occurs nowhere in that sequence. This condition must be tested against the current sequence, not against an earlier one.

Missing Labels and Leaves

Proof. We first prove the encoding statement by induction on the number of vertices. For two vertices, the code is empty and both vertices are leaves, so the claim holds. Now let \(T\) have at least three vertices, let \(x\) be the leaf removed first, and let \(y\) be its neighbor. The code starts with \(y\); its remaining entries are the code of \(T-x\), where \(T-x\) is the tree after deleting \(x\). The label \(x\) cannot occur in that remaining code, so \(x\) is absent from the full code and is a leaf of \(T\). For any other vertex \(v\ne y,x\), deleting \(x\) does not change whether \(v\) is a leaf, and the first code entry \(y\) does not change whether \(v\) is absent. The induction hypothesis applies to \(T-x\), so the claim holds for these vertices. For \(y\), the first entry makes \(y\) present in the full code. Also, adding the edge \(xy\) to \(T-x\) increases the number of edges incident to \(y\) by one: if \(y\) was a leaf in \(T-x\), it is not a leaf in \(T\); if it was not a leaf, it remains not a leaf. This proves the encoding statement.

For the decoding statement, use induction on the number of current labels. With two labels the sequence is empty, the decoded tree is their single edge, and both labels are leaves. Suppose there are at least three current labels, the sequence begins with \(y\), and \(x\) is the smallest current label absent from the sequence. Decoding attaches \(x\) to \(y\), then decodes the remaining sequence on the remaining labels. By induction, in that smaller decoded tree the absent labels are exactly its leaves. In the full sequence, \(x\) is absent and \(y\) is present. In the decoded tree, \(x\) is a new leaf; adding its edge does not change whether any vertex other than \(y\) is a leaf. The vertex \(y\) gains an incident edge, so it is not a leaf in the full tree, whether or not it was a leaf in the smaller tree. Thus absence from the full sequence agrees with being a leaf for every current label. \(\square\)

Decoding Always Produces a Tree

Proof. We use induction on \(n\). For \(n=2\), decoding the empty sequence joins the two labels, which gives a tree. For \(n\ge3\), let \(x\) be the smallest label absent from the sequence, and let \(y\) be its first entry. As noted above, \(x\ne y\). The rest of the procedure decodes the sequence with its first entry removed on the labels other than \(x\); by induction, this gives a tree on those labels. Adding the new vertex \(x\) with the single edge \(xy\) keeps the graph connected. It cannot create a cycle, because any cycle through \(x\) would require two edges incident to \(x\), while \(x\) has only one. The result is therefore a tree on \([n]\). \(\square\)

The Inverse Procedures

Proof. We prove the two inverse statements by induction on \(n\), with the two-vertex case as the base case. When \(n=2\), encoding the single edge gives the empty sequence, and decoding the empty sequence gives that edge. Both statements hold.

First take a sequence \(c\) of length \(n-2\), where \(n\ge3\), and let \(D(c)\) be its decoded tree. The decoding part of the lemma says that the labels absent from \(c\) are exactly the leaves of \(D(c)\). Consequently, the smallest label chosen by the decoder is the smallest leaf of \(D(c)\), exactly the leaf the encoder chooses. If the first entry of \(c\) is \(y\), the decoder attaches that leaf to \(y\), so the encoder records \(y\) as its first entry. After deleting the leaf, the remaining tree is the tree decoded from the sequence obtained by removing the first entry of \(c\). By induction, encoding that remaining tree returns that remaining sequence. Hence encoding \(D(c)\) returns all of \(c\), in order.

Now take a tree \(T\) on \([n]\), and let its code be \(c\). The encoding part of the lemma says that the labels absent from \(c\) are exactly the leaves of \(T\). Thus the decoder’s first choice, the smallest label absent from \(c\), is the same leaf \(x\) that the encoder removed first. If the encoder records the neighbor \(y\), then \(c\) begins with \(y\). Decoding therefore adds the edge \(xy\), just as in \(T\), and continues with the code of \(T-x\) on the remaining labels. By induction, decoding that remaining code reconstructs \(T-x\). Adding back \(xy\) reconstructs \(T\). The two procedures are inverse in both directions. \(\square\)

Worked Examples

Why the Bijection Matters

A bijection guarantees that every allowed sequence represents exactly one labeled tree and every labeled tree has exactly one such sequence. The proof depends on a precise matching of choices: the smallest missing label in the current sequence is the smallest leaf in the current tree. This correspondence supports later counting arguments, but its value here is more basic: it shows that neither procedure loses information, even when a sequence repeats labels.

Common pitfall: using the original sequence at every step. For \((4,4,4)\), the labels absent from the original sequence are \(\{1,2,3,5\}\). Choosing the smallest of those repeatedly would choose \(1\) each time and attempt to add \(14\) three times, which is not the decoding rule and does not produce the required tree. After each step, remove the chosen label and the first sequence entry, then find missing labels in the updated sequence among the updated labels. In this example those choices are \(1\), then \(2\), then \(3\); the successive recorded-neighbor edges are \(14,24,34\).