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

\frametitle{Lecture 24: Eulerian Trails and Circuits}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{5mm}
Grimaldi 11.3

\vspace{1cm}
\includegraphics[height=4cm]{konigsbergfig.jpg} 

\bigskip
Question: Is it possible walk around the city crossing each bridge exactly once, and
end up where you started?
\vspace{1cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%\begin{theorem}
%Every connected graph $G=(V,E)$ with $|V| \ge 2$ has at
%least two vertices $v_1$ and $v_2$ so that $G-v_1$ and $G-v_2$ are both connected.
%\end{theorem}
%Example
%\vspace{2cm}
%Proof
%
%\end{frame}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%Proof (cont.)
%
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Eulerian circuit ]
An {\bf Euler ciruit} of a multi-graph $G=(V,E)$ is a circuit
$$ W = v_1, e_1, v_2, e_2, \dots, e_n, v_1 $$
such that every edge in $E$ appears once in $W$.
\end{definition}

Examples.

\vspace{8cm}

\end{frame}

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

\begin{lemma}
Let $G=(V,E)$ be a multigraph with $|E| \ge 1$.  \\
If $\deg(v) \ge 2$ for all $v \in V$, then $G$ contains a cycle of length $\ge 1$.
\end{lemma}

\medskip
Proof.

\vspace{9cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont).

\vspace{12cm}
\end{frame}

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

\begin{theorem}[ Euler ]
A connected multigraph $G=(V,E)$ which is not the singleton vertex,
has an Euler circuit if and only if every vertex in $V$ has even degree.
\end{theorem}

\medskip
Proof.

\vspace{12cm}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont.)

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont.)

\vspace{8cm}

{\bf The proof gives a recursive algorithm for finding an Euler circuit!}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}
An {\bf Euler trail} of a multi-graph $G=(V,E)$ is a trail
$$ T = v_0, e_1, v_1, e_2, \dots, e_n, v_n $$
such that every edge in $E$ appears once in $T$.
\end{definition}

Example
\vspace{3cm}

\begin{corollary}[ of Euler's theorem ]
A connected multigraph $G=(V,E)$ has an Euler trail 
if and only if there are exactly two vertices in $G$ of odd degree.
\end{corollary}

Proof. Exercise.
\end{frame}


