= Solution
Encode a <labelled tree> by repeatedly deleting its smallest-labelled <leaf of a graph> and recording its neighbor, stopping when two <vertices> remain. This produces a sequence of length $n-2$ with entries in $\{1,\ldots,n\}$.
Conversely, given such a sequence, at each step choose the smallest unused label not occurring in the remaining sequence, join it to the first sequence entry, delete that chosen label and the first entry, and continue. Finally join the two labels left over. A label outside the remaining sequence always exists because two more labels than entries remain. The process never uses a previously deleted label as a sequence entry. Each step attaches a new <leaf of a graph> to the eventual remaining graph, so backward <induction> shows that the result is <connected> and acyclic, hence a <tree>.
In a <tree> encoding, a <vertex> occurs once for every incident <edge> except the <edge> by which it is eventually removed, or the final surviving <edge>. Thus its number of occurrences is its <vertex degree>[degree] minus one. The labels absent from the current remaining sequence are exactly the current <leaves of a graph>. Both procedures therefore choose the same smallest <leaf of a graph> and <edge> at every stage. They are <inverse element>[inverse] maps, proving the claimed <bijection>, including the empty sequence when $n=2$.
Back to article page
