Bijection between Prüfer Sequences and Labeled Trees
Jump to navigation
Jump to search
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.
$\blacksquare$