%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Class Notes: Graph Counting
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 5: Counting in Graphs}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}
\bigskip

Grimaldi 11.1, 11.3

\bigskip
\bigskip

\quad \includegraphics[height=4.0cm]{Wheel5.png}

\quad \quad The Wheel graph $W_5$.

\bigskip
Problem: How many cycles does $W_5$ have?

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Draw the graph $G=(V,E)$ where $V=\{1,2,3,4,5\}$ and 
$E=\{\{1,3\},\{1,4\},\{2,4\},\{2,5\}\}$.

\vspace*{4.5cm}

\begin{definition} [ Bipartite graph ]
A graph $G=(V,E)$ is \textbf{bipartite} if we can partition the vertices
in $V$ into two non-empty sets $V_1$ and $V_2$ such that
\begin{itemize}
\item[(1)] \  $V_1 \cap V_2 = \emptyset$
\item[(2)] \  $V_1 \cup V_2 = V$
\item[(3)] \  every edge in $E$ is incident with one vertex in $V_1$ and one vertex in $V_2$.
\end{itemize}
\end{definition}

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

\begin{definition}[ \ $K_{m,n}$ \ ]
For integers $n \ge 1$ and $m \ge 1$ we define the \textbf{complete bipartite graph} 
$K_{m, n}$ to be the bipartite graph with
$|V_1| = n$,  $|V_2| = m$ and 
$$E = \{  \{ v_1, v_2\} \mid \mbox{$v_1 \in V_1$ and $v_2 \in V_2$} \}.$$  
\end{definition}

Example $K_{2,3}$

\vspace{7cm}
\end{frame}


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

Question 1: How many edges are in a path on $n$ vertices? \\
Question 2: How many edges are in a cycle on $n$ vertices?


\vspace{3cm}


Question 3:  How many edges are in $K_n$ ? \\
Question 4:  How many edges are in $K_{m,n}$ ?
\vspace{5cm}
\end{frame}


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

Question 5: How many graphs are there with $n$ vertices? \\
Question 6: How many graphs have $n$ vertices and $m$ edges?

\vspace{3cm}

Let $V_1, V_2$ be disjoint sets with $|V_1| = n_1$ and $|V_2| = n_2$. \\
Question 7: How many graphs have bipartition $(V_1, V_2)$? \\
Question 8: How many graphs have bipartition $(V_1, V_2)$ with $m$ edges?

\vspace{3.5cm}
\end{frame}



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

\begin{definition}[ \ Subgraph \ ]
Let $G = (V,E)$ and $G'=(V',E')$ be two graphs. \\
$G'$ is a \textbf{subgraph} of $G$ if $V' \subseteq V$ and $E' \subseteq E$. \\
If $V' = V$ then we call $G'$ a \textbf{spanning} subgraph of $G$.
\end{definition}

Example.

\vspace{2cm}

\noindent
Question 9: How many spanning subgraphs does $K_{n_1,n_2}$ have? \\
Question 10: How many spanning subgraphs of $K_{n_1, n_2}$ have exactly $m$ edges?  

\vspace{4cm}

\end{frame}

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

\begin{definition} [ Paths and Cycles ]
If $P$ is a subgraph of $G$ that is a path we call $P$ \textbf{a path of $G$}.\\
If $C$ is a subgraph of $G$ that is a cycle we call $C$ \textbf{a cycle of $G$}.
\end{definition}


Example.

\includegraphics[height=3.5cm]{PetersenGraph.png}

Question 11: How many $4$-vertex paths does the graph $K_n$ have?

\vspace{3cm}
\end{frame}




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

\begin{definition}[ \  induced subgraph \ ]
Let $G = (V,E)$ be a graph and let $V' \subseteq V$.
The subgraph of $G$ \textbf{induced} by $V'$ is the graph
$G' = (V', E')$ where 
$$ E' = \{ \{ x,y \} \mid x \in V', y \in V' {\rm and} ~~ \{x,y\} \in E \}. $$
\end{definition}

For the graph below determine the induced subgraph for the vertex sets
$\{1,3,4\}$ and $\{1,0,3,4\}$.

\includegraphics[height=3.5cm]{Wheel5.png}
	

\vspace{3cm}
\end{frame}

