= Prüfer sequence
{c}
{title2=$p=(p_1,\ldots,p_{n-2})$}
{wiki}
= Prüfer code
{c}
{synonym}
For $n\geq2$, a <Prüfer sequence> is the encoding of a <labelled tree> on $\{1,\ldots,n\}$ by a <sequence>
$$
p=(p_1,\ldots,p_{n-2})\in\{1,\ldots,n\}^{n-2}.
$$
Repeated 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. https://users.math.msu.edu/users/magyarp/math481/[Peter Magyar, Math 481: Prüfer encoding with the smallest leaf]{ref}
For a concrete example, take six <vertices> and the set of <edges>
$$
E=\bigl\{\{1,2\},\{1,3\},\{3,4\},\{3,5\},\{5,6\}\bigr\}.
$$
Initially $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> is
$$
p=(1,3,3,5).
$$
The 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.
\Image[/pruefer-tree-encoding.png]
{title=Encoding a six-<vertex> <tree> as the <Prüfer sequence> $(1,3,3,5)$, then reconstructing its five <edges>}
To decode, keep a set $L$ of remaining labels, initially $\{1,\ldots,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:
|| Remaining <sequence> before the step
|| Smallest absent remaining label
|| <Edge> added
| $(1,3,3,5)$
| $2$
| $\{2,1\}$
| $(3,3,5)$
| $1$
| $\{1,3\}$
| $(3,5)$
| $4$
| $\{4,3\}$
| $(5)$
| $3$
| $\{3,5\}$
| Empty; $L=\{5,6\}$
| Final pair
| $\{5,6\}$
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. https://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf[Columbia University, Graph Theory Lecture 4: Prüfer degree identity, decoding algorithm, and bijection]{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>. https://i.sstatic.net/WDvxyMwX.png[Prüfer (1918), original opening-page scan, page 142]{ref}
Back to article page
