\begin{frame}
\frametitle{Lecture 6: Graph Isomorphism}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}
\bigskip

Grimaldi 11.2

Which of the following graphs are the ``same'' ?
\bigskip

\quad \includegraphics[height=3cm]{G2.png} 
\quad \includegraphics[height=3cm]{G1.png} 
\quad \includegraphics[height=3cm]{G3.png}

\vspace*{5cm}
\end{frame}

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

\begin{definition} [ isomorphic graphs ]
Let $G=(V_1,E_1)$ and $H=(V_2,E_2)$ be two graphs.  Then 
$G$ is {\bf isomorphic} to $H$ (has the same structure as) if there is a bijection
$f: V_1 \rightarrow V_2$ such that
$$ \{u,v\} \in E_1 \Longleftrightarrow \{f(u),f(v)\} \in E_2 . $$
The function $f$ is called an {\bf isomorphism}.
\end{definition}

Example.

\vspace{6cm}

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

Example.  Draw all non-isomorphic graphs with $|V|=3$ and $|V|=4$.

\vspace*{8cm}

Exercise.  Draw all non-isomorphic graphs with 5 vertices and 4 edges.

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

How can we test if two graphs $G$ and $H$ are isomorphic?

\vspace*{8cm}

An ``efficient'' graph isomorphism algorithm is not known.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example.  For $n \ge t$, how many subgraphs of $K_n$ are isomorphic to $K_t$ ?
 
\vspace*{9cm}

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

Example.  Let $K_4^-$ be $K_4$ less one edge. \\
How many subgraphs of $K_n$ are isomorphic to $K_4^-$?

\vspace*{8cm}

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

Example. How many subgraphs of $K_{n,m}$ are isomorphic to $K_{3,4}$?
\vspace*{9cm}

\end{frame}

