Prüfer encoding and decoding are inverse bijections between labelled trees on $n\ge 2$ vertices and words of length $n-2$ on their labels

On a two-element natural-label set, the only word is empty and the only tree is the edge joining the labels, so encoding and decoding agree.

Assume that encoding and decoding are inverse on every finite natural-label set of size $n-1$.

Let $w=a_0\cdots a_{n-3}$ and let $v$ be the least label absent from $w$. Decoding first attaches $v$ to $a_0$ and never uses $v$ again.

Conversely, let $T$ be a labelled tree, let its first encoding operation delete the least leaf $u$, and let it record the neighbour $b$.

In the decoded tree, $v$ is a leaf. Every label smaller than $v$ occurs in $w$, so while it is unused it receives an edge as a recorded neighbour and later receives its deletion edge or the final edge. Hence no smaller label is initially a leaf, and encoding first deletes $v$ and records $a_0$.

The label $u$ is absent from the full code. Every smaller label is not initially a leaf, so before it can be deleted, deletion of an incident leaf records it at least once. Thus $u$ is the least label absent from the code, and decoding first restores the edge $ub$.

After removing $v$ and the first word entry, both procedures operate on the same ordered label set of size $n-1$ and the suffix word. The induction hypothesis shows that the remaining operations are inverse. Thus encoding the decoded tree returns $w$.

After deleting $u$ and the first code entry, the induction hypothesis restores the remaining tree on its ordered label set of size $n-1$. Therefore decoding the code of $T$ returns $T$.

Both composites are identities, so encoding and decoding are inverse bijections on the ordered label set of size $n$. Applying this to the natural order on $n$ proves the theorem.