Lesson 4

Proof. [Proof (Prüfer, 1918)] We construct a bijection between all trees and \(\{0,1,\dotsc,n-1\}^{n-2}\). For this, we associate each tree with the so-called Prüfer code and show how to reconstruct the tree from the code.

Among all vertices of the tree, we take the leaf \(l\) with the smallest number, write its neighbor \(p\) into the code, and remove \(l\) from the tree. After that, we continue recursively. We stop the recursion at the moment when only two vertices remain in the tree. Intuitively, we should stop at this moment because a tree of two vertices does not need encoding (it is enough to know the labels of both vertices).

The constructed code satisfies the following natural property: the vertex \(v\) appears in the code exactly \(\deg(v)-1\) times. In the process of constructing the Prüfer code, the degree of \(v\) will decrease until \(v\) itself becomes a leaf. With each decrease, \(v\) will be added to the Prüfer code. However, when \(v\) itself becomes a leaf, it can no longer appear in the code. Accordingly, the leaves of the original tree will not appear in the code at all. Let's verify that our intuition is correct: the length of the Prüfer code will be \[\sum_{v}\left(\deg(v)-1\right)=\left(\sum_{v}\deg(v)\right)-n=n-2  .\]

The observation above will help us understand how to reconstruct the original tree from the given code \((p_{1}, \dotsc, p_{n-2})\). We know that in the first step, the leaf with the smallest number was removed. This allows us to determine from the code which leaf it was: it is simply the smallest number \(l\) from \(\{0,\dotsc,n-1\}\) that does not appear in the code! Thus, we can reconstruct the first removed edge of the tree \(\{l, p_{1}\}\). Everything else can be restored recursively: we know that after removing the first edge, the Prüfer code is constructed for the remaining tree recursively. We just need to remember that the labels of the remaining tree are \(\{0,\dotsc,n-1\} \setminus \{l\}\). The recursive procedure should stop when the code becomes empty. At this moment, the label set will contain two vertices. These vertices should simply be connected by an edge.◼