Determine which trees have Pr¨ufer codes that (a) contain only one value, (b) containexactly two values, or (c) have distinct values in all positions.

Solution

1. Prufer code contains only one value

• Let the Prufer code $P = [k, k, \dots, k]$.

• Steps*:

1. Number of vertices:

   • The Prufer code has a length of $n-2$, so the tree has $n$ vertices. These vertices are ${1, 2, \dots, n}$.

2. Decoding the Prufer code:

   • In each step of the decoding process, the smallest leaf is selected and is made adjacent to the vertex corresponding to the first value in the Prufer code.
   • Since the Prufer code consists entirely of the value $k$, each leaf will be adjacent to vertex $k$.

3. Center vertex $k$:

   • During the decoding process, all other vertices are sequentially removed as leaves, each connecting to vertex $k$.
   • At the end of the decoding process, the only remaining vertex with a degree higher than 1 is vertex $k$.
   • This means that all the other $n-1$ vertices are leaves adjacent to $k$.

Conclusion:

• The resulting tree is a star tree, where the center vertex is $k$.

---

2. Prufer code contains exactly two values

• If the Prufer code alternates between two values $a$ and $b$, like $[a, b, a, b, \dots]$, then:
  • Vertices $a$ and $b$ are adjacent to each other.
  • Both $a$ and $b$ have multiple leaves connected to them.

---

3. Prufer code contains distinct values in all positions
Steps:

1. Each value in the Prufer code represents the vertex adjacent to a leaf that is being removed from the tree.
2. If all values in the Prufer code are distinct, then every time a leaf is removed, a new leaf appears, and each vertex can become a leaf only once.
3. The structure of the tree is formed linearly because:
   • No branching occurs.
   • No new leaves are created.

Conclusion:

• When the Prufer code finishes, the remaining two vertices are adjacent, forming the final edge in the tree.
• The resulting tree is a single straight path.