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

\frametitle{Lecture 28:  Trees}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 12.1

\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ tree, forest and leaf ]
Let $G=(V,E)$ be a multigraph.  
$G$ is a {\bf tree} if $G$ is connected and $G$ does not contain a cycle.
$G$ is a {\bf forest} if $G$ does not contain a cycle.
A vertex of degree 1 is called {\bf leaf} or {\bf pendant vertex}.
\end{definition}

\medskip
Examples

\vspace{4cm}
Since a tree cannot have loops or parallel edges, it is a simple graph. \\
We previously showed that every graph with all vertices
of degree $\ge 2$ must have a cycle.  Therefore, every tree with $\ge 2$
vertices must have a leaf.
Later we will see that all trees with at least two vertices have at least two leaves.

\end{frame}


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

\begin{lemma}
If $T=(V,E)$ is a tree with leaf $v$ then $T-v$ is a tree. 
\end{lemma}

\medskip
Proof

\vspace{5.5cm}

This observation gives us a powerful tool for proving properties of trees.
Try using induction on the number of vertices and, for the
inductive step, deleting a leaf then applying the inductive hypothesis.

\end{frame}

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

\begin{theorem}[ unique paths ]
If $T=(V,E)$ is a tree and $u,v \in V$ are distinct,
there is a unique path in $T$ with ends $u,v$.
\end{theorem}

\medskip
Proof.

\vspace{8cm}
\end{frame}

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

\begin{theorem}[ main property of trees ]
If $T=(V,E)$ is a tree then $|V|=|E|+1$. \\
If $G=(V,E)$ is a forest with $k$ trees then $|V|=|E|+k.$
\end{theorem}

\medskip
Proof.

\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont).
\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{lemma}
If $G=(V,E)$ satisfies $|V|=|E|+1$ then $G$ must have
a vertex of degree 0 or at least two of degree 1.
\end{lemma}

\medskip
Proof.

\vspace{10cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{lemma}
Every tree $T=(V,E)$ with $|V|\ge 2$ has at least two leaves.
\end{lemma}

\medskip
Proof.
\vspace{6cm}

Exercise.  
Let $T$ be a tree.  Show that removing any edge from $T$ disconnects $T$.
\end{frame}

