Bijection between Prüfer Sequences and Labeled Trees

From ProofWiki
Jump to: navigation, 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.


Hence the result.

$\blacksquare$