\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{ Lecture 32 \ Labelled Trees and Pr\"ufer Sequences }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}

Grimalid 12.1 Exercise 21

\vspace{2cm}
{\bf Question:} How many trees with labels $1,2,3,\dots,n$ are there? \\
Equivalently, how many spanning trees are there in $K_n$?

\vspace{2cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf Question:} How many trees with labels $1,2,3,\dots,n$ are there? \\
Equivalently, how many spanning trees are there in $K_n$? \\
Let $T_n$ be the set of such trees and let $t_n = |T_n|$.

\bigskip
\bigskip
\bigskip
\bigskip


\includegraphics[height=4cm]{cayley.png}

$T_1, T_2, T_3, T_4$ using colors for labels. \\
We have $t_1=1, t_2=1, t_3=3, t_4=16$.

\bigskip
\bigskip

What is $t_n$?
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem} [ Cayley's formula for the number of labelled trees ]
The number of spanning trees of $K_n$ is 
{\large \color{blue} $\ds t_n = n^{n-2}$} for $n \ge 2.$
\end{theorem}

\medskip
Proof -- Heinz Pr\"ufer, 1918.

\medskip
Let $T_n$ be the set of labelled trees on $n$ vertices. \\
Let $P_n$ be the set of sequences in $V = \{1,2,\dots,n\}$ of length $n-2$. \\
The Pr\"ufer code is a function $Pru : T_n \rightarrow P_n.$ \\
We will show that Pru is a bijection hence $|T_n| = | P_n | = n^{n-2}$.

\vspace{4.5cm}
See the youtube video on Cayley's Formula by Sarda Herke.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Algorithm $Pru(T)$ \\
Input: A tree $T$ on $n$ vertices. \\
Output: A Pr\"ufer code $x \in P_n$ of length $n-2$.
\begin{itemize}
%\item[1.] If $T$ has two vertices return () the empty sequence.
%\item[2.] Let $u$ be the leaf of $T$ with the smallest vertex label and
%          let $v$ be it's unique neighbour in $T$.
%\item[3.] Return $(v,Pru(T - u))$.
\item[1.] For $i=1,2,\dots,n-2$ do \\
\quad  Let $u$ be the leaf in $T$ with smallest vertex label. \\
\quad  Set $x_i$ to be the unique neighbor of $u$ in $T$. \\
\quad  Remove the vertex $u$ and edge $\{u,x_i\}$ from $T$.
\item[2.] Return $(x_1,x_2,\dots,x_{n-2})$.
\end{itemize}

\medskip
Example.
\vspace{4.5cm}


Notice that the number of times a vertex $v$ appears in $Pru(T)$ is $\deg(v)-1$.
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Algorithm Tree($\bf x$). \\
Input $V = {v_1,v_2,\dots,v_n}$ and a Pr\"ufer code $x$ of length $n-2$ on $V$. \\
Output a tree with vertices $V$
\begin{itemize}
\item[1.] Set $L = V$ and $E = \phi$.
\item[2.] For $i=1,2,\dots,n-2$ do \\
\quad    Let $y$ be the first element in $L$ that is not in $x[i..n-2]$. \\
\quad    Set $E = E \cup \{x_i,y\}$ and remove the vertex $y$ from $L$.
\item[3.] Set $E = E \cup L$.
\item[4.] Return the tree $(V,E)$.
\end{itemize}

\medskip
Example.  Determine the tree for the Pr\"ufer code $3,4,5,3,1$.

\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Additional Space.

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Additional Space.

\vspace{12cm}
\end{frame}
