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.
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 proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
$\blacksquare$
