Bijection between Prüfer Sequences and Labeled Trees

Theorem

There is a one-to-one correspondence between Prüfer sequences and labeled trees.

That is, every labeled tree has a unique Prüfer sequence that defines it, and every Prüfer sequence defines just one labeled tree.

Proof

Let $T$ be the set of all labeled trees of order $n$.

Let $P$ be the set of all Prüfer sequence of length $n-2$.

Let $\phi: T \to P$ be the mapping that maps each tree to its Prüfer sequence.

• From Prüfer Sequence from Labeled Tree, $\phi$ is clearly well-defined, as every element of $T$ maps uniquely to an element of $P$.

• However, from Labeled Tree from Prüfer Sequence, $\phi^{-1}: P \to T$ is also clearly well-defined, as every element of $P$ maps to a unique element of $T$.

Hence the result.

The validity of the material on this page is questionable. In particular: How is it immediate that the two constructions are mutually inverse? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

$\blacksquare$