Find X so that the graph resulting from decoding the Prufer sequence 1,1,7,X,3,3,7,6,7 has all vertices with an odd degree

Question

Find x so that the graph resulting from decoding the Prufer sequence 1,1,7,X,3,3,7,6,7 has all vertices with an odd degree. The graph has 10 vertices (1,2,3,4,5,6,7,8,9,10).

I didn't know how to find X, so instead I tried a brute force approach. I chose a value from 1 to 10, replaced it with X in the sequence, and decoded the sequence. However, all the time, in the resulting graph at least one vertex had an even degree. What am I doing wrong?

When X = 1 this is the graph I get. At some point while decoding I run out of numbers, so as not to add 11 I use 1 again (because the problem says |V|=10)

Answer 1

You should see there is something wrong, since the graph you posted has a cycle.

The problem here is that you are mixing up Prüfer sequences for unrooted trees with Prüfer sequences for rooted trees. The former is a bijection between lists of length $n-2$ with unrooted trees, and the latter is a bijection between lists of length $n-1$ with rooted trees. Your sequence must fall in the latter case, since it has length $9$.

In the rooted case, the bijection is slightly different; for a list $a_1,a_2,\dots,a_{n-1}$, you form a tree by, for each $i$ from $1$ to $n-1$, finding the the current smallest vertex without a parent and not appearing in $a_i,a_{i+1},\dots,a_{n-1}$, and making its parent $a_i$. For example, when $X=1$, the correct result of the bijection is the following rooted tree, where $7$ is the root.

        7
      / | \ 
     3  5  6
    / \    |
   1   9   10
 / | \
2  4  8

I believe this is equivalent to ignoring the last sequence element, using the unrooted Prüfer bijection to make an unrooted tree from the first $n-2$ symbols, and then having the last symbol be the root.

Hint

To solve your problem, you only need these basic facts about the rooted Prüfer correspondence:

• The number of times each index $i$ appears in the sequence corresponds to the number of children that $i$ has in the corresponding rooted tree.

• The degree of a vertex is $1+(\text{# children})$, unless that child is the root, in which case the degree is the number of children.

• The root of the tree corresponding to a sequence is the last entry of that sequence (so $7$ is the root for your sequence, no matter what $X$ is).