Prüfer sequence ($p=(p_1,\dots ,p_{n-2})$)

For $n\ge 2$, a Prüfer sequence is the encoding of a labelled tree on $\{1,\dots ,n\}$ by a sequenceRepeated labels are allowed, and their order matters. To encode the tree, repeatedly remove its smallest-labelled leaf of a graph together with its incident edge, recording the label of its unique neighbour. Stop when two vertices remain; do not record their final edge. Removing a leaf of a graph leaves a tree, so the procedure makes exactly $n-2$ deletions. The choice of the smallest label makes the encoding deterministic. ^[ref]

For a concrete example, take six vertices and the set of edgesInitially $2,4,6$ label the vertices of vertex degree one. Remove $2$ and record its neighbour $1$. Now $1$ has become a leaf of a graph, so remove $1$ and record $3$. Next remove $4$ and record $3$ again; then remove $3$ and record $5$. The final edge joins $5$ and $6$. Thus the Prüfer sequence isThe deletion order is $2,1,4,3$: removing a leaf of a graph can make its neighbour a leaf of a graph, so the eligible labels change as the tree shrinks.

To decode, keep a set $L$ of remaining labels, initially $\{1,\dots ,n\}$, and the remaining sequence, initially $p$. While the sequence is nonempty, let $v$ be the smallest label in $L$ absent from the entire remaining sequence. Add an edge between $v$ and its first entry, then remove $v$ from $L$ and delete that first entry. Finally join the two labels left in $L$. For the example:

The decoder always has a choice: if the remaining sequence has length $m$, then $L$ has $m+2$ labels, so at least two of them are absent. Its first entry is still in $L$, and differs from the chosen absent label. Every removed vertex attaches to a vertex that survives longer; following these attachments eventually reaches the final pair. Consequently the decoded graph is connected, and its $n-1$ edges make it a tree. In this construction, each occurrence of $v$ contributes an incident edge, and $v$ gets one more edge at its final attachment. Thus a remaining label is absent from the remaining sequence exactly when it labels a leaf of a graph. Encoding and decoding choose the same smallest label at each step and undo each other. This bijection proves Cayley's formula and explains why every freely chosen sequence is valid. ^[ref]

For $n=2$ there is exactly one empty sequence, and decoding adds the sole edge. For $n=1$ there is one tree, with vertex degree zero, but no length-$n-2$ Prüfer sequence. This is the exception both to the encoding convention and to the Prüfer degree formula.

Heinz Prüfer's 1918 paper "Neuer Beweis eines Satzes über Permutationen" appeared in Archiv der Mathematik und Physik, third series, volume 27, pages 142–144. It gives an encoding proof of the labelled tree count. The historical title means "New proof of a theorem on permutations"; the modern Prüfer sequence permits repeated labels, so it is not a permutation. ^[ref]