Build Tree by Prüfer Code $(6,2,2,6,2,5,10,9,9)$

Question

I have the Prufer Code $(6,2,2,6,2,5,10,9,9)$.

I want to build the corresponding tree.

My algorithm:

1) Tree = $\{\}$, code = $(6,2,2,6,2,5,10,9,9)$, count = $(1,2,3,4,5,6,7,8,9,10,11)$

2) Tree =$\{(2,6)\}$, code = $(2,2,6,2,5,10,9,9)$, count = $(1,3,4,5,6,7,8,9,10,11)$

3) Tree =$\{(2,6), (2,3)\}$, code = $(2,6,2,5,10,9,9)$, count = $(1,4,5,6,7,8,9,10,11)$

4) Tree =$\{(2,6), (2,3), (2,4)\}$, code = $(6,2,5,10,9,9)$, count = $(1,5,6,7,8,9,10,11)$

5) Tree =$\{(2,6), (2,3), (2,4),(5,6)\}$, code = $(2,5,10,9,9)$, count = $(1,6,7,8,9,10,11)$

6) Tree =$\{(2,6), (2,3), (2,4),(5,6), (2,6)\}$, code = $(5,10,9,9)$, count = $(1,7,8,9,10,11)$

7) Tree =$\{(2,6), (2,3), (2,4),(5,6), (2,6),(5,7)\}$, code = $(10,9,9)$, count = $(1,8,9,10,11)$

8) Tree =$\{(2,6), (2,3), (2,4),(5,6), (2,6),(5,7),(8,10)\}$, code = $(9,9)$, count = $(1,9,10,11)$

9) Tree =$\{(2,6), (2,3), (2,4),(5,6), (2,6),(5,7),(8,10),(9,10)\}$, code = $(9)$, count = $(1,9,11)$

10) Tree =$\{(2,6), (2,3), (2,4),(5,6), (2,6),(5,7),(8,10),(9,10), (9,11)\}$, code = $()$, count = $(1,9)$

11) Tree = $\{(2,6), (2,3), (2,4),(5,6), (2,6),(5,7),(8,10),(9,10), (9,11),(1,9)\}$

Is my solution correct?

Answer 1

I would suggest it goes like this:

Let us first count the degrees of the nodes in the Prüfer Code, ie. count how many times they appear:

$$ \begin{array}{c|c} \text{node}&6&2&5&10&9\\ \hline \text{degree}&2&3&1&1&2 \end{array} $$

Thus $6$ has to have appeared twice as a neighbor of a removed vertex before it could have been removed itself. Similarly $2$ must have three leaves that are removed before it itself becomes a removable leave.

The vertices that can be removed, the free nodes, must be those NOT in the Prüfer Code.

Thus:

 T={}, code=(6,2,2,6,2,5,10,9,9), free=(1,3,4,7,8,11)
 T={(1,6)}, code=(2,2,6,2,5,10,9,9), free=(3,4,7,8,11)
 T={(1,6),(3,2)}, code=(2,6,2,5,10,9,9), free=(4,7,8,11)
 T={(1,6),(3,2),(4,2)}, code=(6,2,5,10,9,9), free=(7,8,11)
 T={(1,6),(3,2),(4,2),(7,6)}, code=(2,5,10,9,9), free=(6,8,11)
 T={(1,6),(3,2),(4,2),(7,6),(6,2)}, code=(5,10,9,9), free=(2,8,11)
 T={(1,6),(3,2),(4,2),(7,6),(6,2),(2,5)}, code=(10,9,9), free=(5,8,11)
 T={(1,6),(3,2),(4,2),(7,6),(6,2),(2,5),(5,10)}, code=(9,9), free=(8,10,11)
 T={(1,6),(3,2),(4,2),(7,6),(6,2),(2,5),(5,10),(8,9)}, code=(9), free=(10,11)
 T={(1,6),(3,2),(4,2),(7,6),(6,2),(2,5),(5,10),(8,9),(10,9)}, code=(), free=(9,11)

And finally we must connect the remaining two, namely (9,11).

Answer 2

We can use the following algorithm (from here) to generate a spanning tree (on $n$ vertices) of $K_n$, given the corresponding Prüfer sequence (of length $n-2$), since there exists a 1-1 mapping always, in between set of all spanning trees of labeled graph $K_n$ (there are $n^{n-2}$ spanning trees of $K_n$ by Cayley's theorem) and set of all Prüfer sequences of length $n-2$ .

The following python code implements the above algorithm:

def get_tree(S):
    n = len(S)
    L = set(range(1, n+2+1))
    tree_edges = []
    for i in range(n):
        u, v = S[0], min(L - set(S))
        S.pop(0)
        L.remove(v)
        tree_edges.append((u,v))
    tree_edges.append((L.pop(), L.pop()))
    return tree_edges

Invoking the above function on a Prüfer sequence, we can obtain the corresponding spanning tree of $K_{11}$, as shown below:

S = [6,2,2,6,2,5,10,9,9]
T_E = get_tree(S)

The next figure shows the final tree:

The following animation shows the tree-building steps: