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

\frametitle{Lecture 26: Planar Graphs continued}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

Grimaldi 11.4

\vspace{3cm}
{\bf Question:} Can a given electronic circuit be layed out on an circuit board
such that no wires cross each other?

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
{\bf Review:} A graph $G=(V,E)$ is {\bf planar} if $G$ has a drawing 
(in the plane) where the edges intersect only at the vertices of $G$.
Such a drawing is called a {\bf planar embedding} of $G$.
The embedding partitions the plane into at set $F$ of regions called {\bf faces}.
We proved Euler's formula $|V| - |E| + |F|=2$.

\medskip
Examples.

\vspace{8cm}

\end{frame}


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

\begin{definition}[ Face degrees ]
Let $G=(V,E)$ be a connected multigraph embedded in the plane
and let $f$ be a face of this embedding.
We define the {\bf degree} of $f$, denoted $\deg(f)$, to be the number
of edges in a facial walk of $f$.
\end{definition}

\medskip
Example
\vspace{3cm}
\begin{theorem}
If $G$ has faces $f_1,f_2, \dots,f_k$ then \ $\ds \sum_{i=1}^{k} \deg(f_i) = 2|E|$.
\end{theorem}
Proof

\vspace{1cm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

What is the maximum number of edges a planar simple graph can have?

\medskip

\begin{theorem}[ Bound 1 for the number of edges ]
If $G=(V,E)$ is a connected planar simple graph with $|V| \ge 3$ then
$$ |E| \le 3 |V|-6 \quad {\rm and} \quad 2|E| \ge 3 |F|. $$
\end{theorem}
\medskip
Proof.

\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{corollary}[ to bound 1 for the number of edges ]
The graph $K_5$ is not planar.
\end{corollary}

\medskip
Proof.
\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem}[ Bound 2 for the number of edges ]
If $G=(V,E)$ is a connected planar simple graph with $|V| \ge 3$ 
{\color{blue} and with no cycle of length 3 or less } then
$$ |E| \le 2|V|-4 \quad {\rm and} \quad |E| \ge 2 |F|. $$
\end{theorem}
\medskip
Proof.
\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{corollary}[ to bound 2 for the number of edges ]
The graph $K_{3,3}$ is not planar.
\end{corollary}
\medskip
Proof.

\vspace{8cm}
\end{frame}

% There's not enough time to show this example
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%\frametitle{The 5 Platonic Solids}
%
%The tetrahedron, cube, octagon, dodecahedron, and icosahedron.
% 
%\includegraphics[height=4cm]{PlatonicSolids.jpeg}
%
%\vspace{6cm}
%
%See Example 11.22 on page 547 of Grimaldi
%\end{frame}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%\frametitle{The 5 Platonic Solids - continued}
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Dual graphs ]
Let $G=(V,E)$ be a connected multigraph embedded in the plane.
The vertices of the {\bf dual} multigraph $G^*$ are the faces of $G$.
If two faces $f_i$ and $f_j$ share an edge $e$
then $e^* = \{f_i,f_j\}$ is an edge in $G^*$.
This may be done so that $e^*$ crosses $e$ and $G^*$ also ends
up embedded in the plane.
\end{definition}

Examples.
\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Features of duals}

\begin{itemize}
\item[(1)] Duals only exist for planar graphs
\item[(2)] If $G^*$ is a dual of $G$ then $G$ is a dual of $G^*$ \ !
\item[(3)] The degree of a vertex in $G^*$ is the degree of the corresponding face of $G$.
\item[(4)] The dual of a simple graph may be a multigraph.
\end{itemize}

Examples
\vspace{8cm}
\end{frame}

