Skip to main content

Chapter 25 Cayley's Theorem

Exercises Practice Problems

1.

Find the extended Prufer code for the following trees

  1. .

    Solution.

    \(\begin{array}{cccccccc}\) 2 & 4 & 5 & 6 & 7 & 3 & 1 \\ 3 & 0 & 3 & 0 & 3 & 1 & 0 \end{array}\(\)

  2. .

    Solution.

    \(\begin{array}{cccccccc}\) 3 & 4 & 5 & 6 & 2 & 1 \\ 1 & 1 & 2 & 2 & 1 & 0 \end{array}\(\)

  3. .

    Solution.

    \(\begin{array}{cccccccccc}\) 6 & 3 & 8 & 4 & 1 & 5 & 9 & 2 & 7 \\ 3 & 1 & 4 & 1 & 5 & 9 &2 & 7 & 0 \end{array}\(\)

2.

What is the Prufer Code for each of the trees in problem 1? Solution.

  1. \(\begin{array}{cccccccc} 3 & 0 & 3 & 0 & 3 & 1 \end{array}\)

  2. \(\begin{array}{cccccccc} 1 & 1 & 2 & 2 & 1 \end{array}\)

  3. \(\displaystyle \begin{array}{cccccccccc} 3 & 1 & 4 & 1 & 5 & 9 &2 & 7 \end{array}\)

3.

Find the tree corresponding to the given Prufer code.

  1. \(\begin{array}{cccccccccc} 2015 \end{array}\) Solution.

  2. \(\begin{array}{cccccccccc} 32103213230 \end{array}\) Solution.

4.

Prove that vertex \(k\) appears \(\deg(k)-1\) times in the Prufer code of a tree. Solution.

As we create the Prufer code, we remove edges one at a time. Each vertex appears as a leaf exactly once, except for vertex \(0\text{.}\) Therefore vertex \(k >0\) appears as the parent of a leaf exactly \(\deg(k)-1\) times. This is also the number of times that \(k\) appears in the second row of the extended Prufer code.

As for vertex 0, it appears \(\deg(0) -1\) times because we delete the final zero in the bottom row of the extended Prufer code in order to get the Prufer code.

5.

Use Cayley's Theorem to prove that there are at least

\begin{equation*} \frac{n^{n-3}}{(n-1)! } \end{equation*}

unlabeled trees on \(n\) vertices.

Solution.

Given an unlabeled tree, the number of distinct labelings is at most \(n!\text{.}\) Therefore

\begin{equation*} n! \cdot (\mbox{# unlabeled trees}) \geq n^{n-2}, \end{equation*}

and the result follows.