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

\frametitle{Lecture 27: Hamiltonian Paths and Cycles }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

Grimaldi 11.5

\bigskip
\bigskip
In 1856 a mathematician William Hamilton invented a game in which the ojbect is to find
a cycle along the edges of a dodecahedron.
\bigskip


\quad \includegraphics[height=4cm]{icosian.jpg} \quad \quad
\includegraphics[height=4cm]{dodec.png}

\medskip
{\bf Problem:} Can you find a cycle in the graph that includes all 20 vertices?

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}
Let $G$ be a graph.  A path of $G$ is a {\bf Hamiltonian path} if it
contains every vertex of $G$.  A cycle of $G$ is a 
{\bf Hamiltonian cycle} if it contains every vertex of $G$.
\end{definition}

\medskip
Examples

\vspace{10cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Algorithm Exhaustive Search: try all possible paths.

\bigskip
\includegraphics[height=4cm]{dodec.png} \quad \quad
\includegraphics[height=4cm]{soccerball.png}

\vspace{5cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Hamiltonian vs. Eulerian}

The definition of Hamiltonian is very similar to Eulerian.
In Hamiltonian each {\color{red} vertex} appears exactly once.  In Eulerian each
{\color{red} edge} appears exactly once.  Although they look similar,
having a Hamiltonian cycle and Having an Euler circuit
is very different.

\begin{itemize}
\item[(1)]
There is a fast algorithm to test if a graph $G=(V,E)$ has an
Euler circuit where the running time is a linear function
of $|V| + |E|$, namely, test if $G$ is connected and all vertices
have even degree.
\item[(2)] No such fast test is known for a Hamiltonian cycle.
The problem of deciding if a graph has a Hamiltonian
path/cycle is {\bf NP-complete}.  So it is widely believed that there
does not exist an algorithm which takes as input an arbitrary
graph $G=(V,E)$ and determines if $G$ has a Hamiltonian path/cycle
where the running time is bounded by a polynomial function of $|V|+|E|$.
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Necessary and sufficient conditions ]
Let $\it P$ be a property of graphs and $C$ be a set of condtions.
\begin{itemize}
\item[(1)] $C$ is {\bf necessary} for $P$ if every graph satisfying $P$ also satisfies $C$.
\item[(2)] $C$ is {\bf sufficient} for $P$ if every graph satisfying $C$ also satisfies $P$.
\item[(3)] If $C$ is both {\bf necessary and sufficient} for $P$, then a graph $G$
       satisfies $P$ if and only if $G$ satisfies $C$.  We say $C$ characterize $P$.
\end{itemize}
\end{definition}

\bigskip
Examples
\begin{itemize}
\item[(1)] It is necessary for a graph to be connected to have a H.P.
\bigskip
\bigskip

\item[(2)] Being a complete graph is a sufficient condition to have a H.P.
\bigskip
\bigskip

\item[(3)] $n>1$ is odd is a necessary and sufficient condition for $K_n$ to have
           an Euler circuit.

\bigskip
\bigskip
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%\frametitle{A necessary condition}
%
%Theorem \ If $G=(V,E)$ is a graph with a Hamiltonian cycle, then
%$G-v$ is connected for every vertex $v \in V$.
%
%\medskip
%Proof.
%\vspace{1cm}
%
%Theorem \ Let $G=(V,E)$ be a bipartite graph with bipartition $V=V_1 \cup V_2$. \\
%If $G$ has a Hamiltonian cycle, then $|V_1|=|V_2|$.
%
%\medskip
%Proof.
%\vspace{7cm}
%
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{A sufficient condition for G to have an Hamiltonian path.}
\begin{theorem}
Let $G=(V,E)$ be a graph with $|V|=n$.  If
\bigskip

\quad $ \ds \deg(x)+\deg(y) \ge n-1 $ \ for all $x,y \in V$ with $x \ne y$

\bigskip
then $G$ has Hamiltonian path.
\end{theorem}

\medskip
Proof.

\vspace{8cm}

\end{frame}

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

\end{frame}

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

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{corollary}
If $G=(V,E)$ is a graph with $|V|=n$ and $\deg(v) \ge \frac{n-1}{2}$ 
holds for every $v \in V$, then $G$ has a Hamiltonian path.
\end{corollary}

Proof.
\vspace{10cm}

\end{frame}

