Skip to main content\(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Worksheet 5.5 Counting Labeled Trees
Activity 5.5.1.
(a)
Construct
\(\prufer(\bfT)\) for the two trees below.
A tree with 6 vertices. The neighbors of each vertex are given in the table below.
| Vertex |
Neighbors |
| \(1\) |
\(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\)
|
| \(2\) |
\(1\) |
| \(3\) |
\(1\text{,}\) \(6\)
|
| \(4\) |
\(1\) |
| \(5\) |
\(1\) |
| \(6\) |
\(3\) |
A tree with 14 vertices. The neighbors of each vertex are given in the table below.
| Vertex |
Neighbors |
| \(1\) |
\(9\) |
| \(2\) |
\(8\text{,}\) \(9\text{,}\) \(10\text{,}\) \(11\text{,}\) \(14\)
|
| \(3\) |
\(11\) |
| \(4\) |
\(12\) |
| \(5\) |
\(6\text{,}\) \(7\text{,}\) \(12\text{,}\) \(14\)
|
| \(6\) |
\(5\) |
| \(7\) |
\(5\text{,}\) \(13\)
|
| \(8\) |
\(2\) |
| \(9\) |
\(1\text{,}\) \(2\)
|
| \(10\) |
\(2\) |
| \(11\) |
\(2\text{,}\) \(3\)
|
| \(12\) |
\(4\text{,}\) \(5\)
|
| \(13\) |
\(7\) |
| \(14\) |
\(2\text{,}\) \(5\)
|
Solution.
\(1113\) is the Prüfer code for the tree on the left.
\((9,11,12,5,2,2,2,2,14,5,7,5)\) is the Prüfer code for the tree on the right.
(b)
Be prepared to answer the following questions:
-
What is the relationship between the length of the Prüfer code of a tree and the number of vertices of the tree?
-
What type(s) of vertices have labels appearing in the Prüfer code of a tree?
(c)
Extra time? Draw a tree for another group to find the Prüfer code of.
Activity 5.5.2.
(a)
Complete the table (and draw the tree) for the Prüfer code
\(8431875\text{.}\)
Solution.
| Prüfer code |
Label set |
Edge added |
| 8431875 |
\(\{1,2,3,4,5,6,7,8,9\}\) |
\(2-8\) |
| 431875 |
\(\{1,3,4,5,6,7,8,9\}\) |
\(6-4\) |
| 31875 |
\(\{1,3,4,5,7,8,9\}\) |
\(4-3\) |
| 1875 |
\(\{1,3,5,7,8,9\}\) |
\(3-1\) |
| 875 |
\(\{1,5,7,8,9\}\) |
\(1-8\) |
| 75 |
\(\{5,7,8,9\}\) |
\(8-7\) |
| 5 |
\(\{5,7,9\}\) |
\(7-5\) |
| (empty string) |
\(\{5,9\}\) |
\(5-9\) |
(b)
Find the tree for the Prüfer code
\(4747313\text{.}\)
Solution.
| Prüfer code |
Label set |
Edge added |
| 4747313 |
\(\{1,2,3,4,5,6,7,8,9\}\) |
\(2-4\) |
| 747313 |
\(\{1,3,4,5,6,7,8,9\}\) |
\(5-7\) |
| 47313 |
\(\{1,3,4,6,7,8,9\}\) |
\(6-4\) |
| 7313 |
\(\{1,3,4,7,8,9\}\) |
\(4-7\) |
| 313 |
\(\{1,3,7,8,9\}\) |
\(7-3\) |
| 13 |
\(\{1,3,8,9\}\) |
\(8-1\) |
| 3 |
\(\{1,3,9\}\) |
\(1-3\) |
| (empty string) |
\(\{3,9\}\) |
\(3-9\) |
(c)
Extra time? Make up a Prüfer code and have another group find the tree.
