Can someone please explain Prufer's sequence?

Question

I'm currently having a difficult time understanding the Prufers sequence. I'm a bit confused on understanding the concept of choosing the smallest node and how to know which nodes connect to which nodes.

For example: Calculate the tree for Prufer's sequence S = [1,3] on four nodes A =[1,2,3,4]. I have been told to choose the smallest number in A, which is not in S, in this case; 2. However, should 2 be connected to 1?

It would be greatly appreciated if you could explain the purpose of using Prufer's sequence, as well as explaining the example above.

Answer 1

The reconstructing algorithm is this:

1. Let $x_1, x_2, \dots, x_{n-2}$ be the Prüfer code; let $x_{n-1} = n$. In this example, starting with the Prüfer code $(1,3)$, we have $(x_1, x_2, x_3) = (1,3,4)$.
2. Let $y_1, y_2, \dots, y_{n-1}$ be defined as follows: $y_i$ is the least integer not appearing in the list $(y_1, y_2, \dots, y_{i-1}, x_i, x_{i+1}, \dots, x_{n-1})$. In this example,
   • $y_1$ is the least integer not appearing in $(x_1, x_2, x_3) = (1,3,4)$: it is $2$.
   • $y_2$ is the least integer not appearing in $(y_1, x_2, x_3) = (2,3,4)$: it is $1$.
   • $y_3$ is the least integer not appearing in $(y_1, y_2, x_3) = (2,1,4)$: it is $3$.
3. The edges of the tree are $x_1y_1, x_2y_2, \dots, x_{n-1}y_{n-1}$: in this case, $12$, $31$, and $43$.

The purpose of Prüfer codes is twofold. First, this is an explicit bijection between sequences of $n-2$ elements of $\{1,2,\dots,n\}$ and the $n^{n-2}$ labeled trees on $n$ vertices. Second, we can recover some information about the tree from its Prüfer code (for example, if a vertex has degree $d$ in the tree, its label appears $d-1$ times in the Prüfer code) and this lets us count some more specific types of labeled trees easily.