\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pstricks}
\usepackage{multicol}



\begin{document}

\title{Episode 21 -- Planar graphs}
\subtitle{European section -- Season 2}
\date{}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}{The three houses problem}

\begin{center}
\LARGE
\begin{tabular}{|c|p{1cm}|c|p{1cm}|c|}
\cline{1-1}\cline{3-3}\cline{5-5}
House 1 && House 2 && House 3 \\
\cline{1-1}\cline{3-3}\cline{5-5}
\multicolumn{5}{c}{\rule{0pt}{3cm}} \\
\cline{1-1}\cline{3-3}\cline{5-5}
Water && Gas && Elec \\
\cline{1-1}\cline{3-3}\cline{5-5}
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Planar and plane graphs}

\begin{center}
\begin{tabular}{ccc}
Plane & Planar & Non-planar \\
\includegraphics[width=3cm]{s02e21/plane.eps} &
\includegraphics[width=3cm]{s02e21/planar.eps} &
\includegraphics[width=3cm]{s02e21/nonplanar.eps} \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Regions of the plane}

\begin{center}
\includegraphics[width=6cm]{s02e21/plane.eps}
\end{center}

\end{frame}

\begin{frame}{Theorem 1 : Euler's formula}

\Large

Let $G$ be a connected plane graph with $p$ vertices, $q$ edges and $r$ regions. Then 
$$p-q+r=2.$$

\end{frame}

\begin{frame}{Theorem 2}

\Large

Let $G$ be a connected plane graph with $p$ vertices, $q$ edges, where $p\geq 3$. Then 
$$q\leq 3p-6.$$

\end{frame}

\end{document}
