Problem
COM-B2-M03-P018 Prüfer Code
Prove that the number of labelled trees on vertices \(1,\ldots,n\) is \(n^{n-2}\).
Build a code of length \(n-2\): each time remove the leaf of smallest label and record its neighbour.
From a tree, build a sequence of length \(n-2\): while more than two vertices remain, remove the leaf of smallest label and record the label of its neighbour. Conversely, from a sequence \(c_1,\ldots,c_{n-2}\), reconstruct the tree: at each step take the smallest label not appearing in the current sequence, connect it to \(c_1\), then remove that label from the vertex set and delete \(c_1\) from the sequence. Finally connect the two remaining vertices.
These procedures are inverse: the leaf removed at each step is exactly the smallest label that will no longer appear in the code. Thus trees are in bijection with sequences of length \(n-2\) over \(n\) labels. There are \(n^{n-2}\) such sequences.
A difficult but very valuable bijection; can be used as a challenge.