\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,graphicx,url}

\begin{document}

\title{General Mathematics and CPS II}
\author{Exercise 3}
\date{February 11, 2015}
\maketitle

\begin{enumerate}

\item Let $G$ be a finite connected planar graph with $V$ its set of
vertices, $E$ its set of edges, and $F$ its set of faces.
\begin{enumerate}
\item Show that $2 \, \lvert E \rvert \geq 3 \, \lvert F \rvert$.
\item Show that $\lvert E \rvert \leq 3 \, \lvert V \rvert - 6$.
\item Conclude that every planar graph must have at least one vertex
of valency less than $6$.
\end{enumerate}

\item The \emph{Petersen graph} can be constructed as the graph whose
vertices are two-element subsets of a five-element set, and two
vertices are joined by an edge whenever the corresponding two-element
sets are disjoint.  It can be visualized as follows.\footnote{Image
from \url{https://commons.wikimedia.org/wiki/File:Petersen1_tiny.svg}}
\begin{center}
\includegraphics[width=0.4\textwidth]{petersen.pdf}
\end{center}

Show that the Petersen graph cannot be embedded in the plane.

%\item Write out the proof for Ivanov, p.\ 96, Lemma 5.

\end{enumerate}
\end{document}
