Chapter 25 Cayley's Theorem
Exercises Practice Problems
1.
Find the extended Prufer code for the following trees
.
.
.
2.
What is the Prufer Code for each of the trees in problem 1?
3.
Find the tree corresponding to the given Prufer code.
\(\displaystyle \begin{array}{cccccccccc} 2015 \end{array}\)
-
\(\begin{array}{cccccccccc} 32103213230 \end{array}\)
4.
Prove that vertex \(k\) appears \(\deg(k)-1\) times in the Prufer code of a tree.
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.