\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{3: Induction!}{Due Tuesday, week 4, at the start of class}



This week is like last week!  To get credit for this problem, just work on it; i.e. think about it, write down ideas, and otherwise spend a hour or two trying to figure out what's going on.  Assignments that show effort (i.e. $>1/2$ page of work and writing, coherent thoughts, good questions for me) will get credit.  If you fully answer the problem, you get the extra-credit half-point as well!

\section*{Checkdown/also extra-credit problem.}
In class, we made a few definitions at the end of class about graphs.  We recap those here, but if you were in class you saw all of these definitions.

\begin{definition}
A \textbf{graph} $G$ with $n$ vertices and $m$ edges consists of the following two objects:
\begin{enumerate}
\item a set $V = \{v_1, \ldots v_n\}$, the members of which we call $G$'s \textbf{vertices}, and
\item a set $E = \{e_1, \ldots e_m\}$, the members of which we call $G$'s \textbf{edges}, where each edge $e_i$ is an unordered pair of elements in $V$.  For a given edge $e = \{v, w\}$, we will often refer to the two vertices $v,w$ contained by $e$ as its endpoints.  In our definition of graph here, notice that we can repeat an edge, and we can also have an edge have both of its endpoints be the same.
\end{enumerate}
\end{definition}


\begin{defn}
We say that a graph $G$ is \textbf{planar} if we can draw it in the plane so that none of its edges intersect.  
\end{defn}


\begin{exmp}
The following pair $(V,E)$ defines a graph $G$ on five vertices and five edges:
\begin{itemize}
\item $V = \{1,2,3,4,5\}$,
\item $E = \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\} \}$.
\end{itemize}
Something mathematicians like to do to quickly represent graphs is \textbf{draw} them, which we can do by taking each vertex and assigining it a point in the plane, and taking each edge and drawing a curve between the two vertices represented by that edge.  For example, one way to draw our graph $G$ is the following:
\begin{center}
\includegraphics[width=1in]{mc2011_introgt_pentagon1.pdf}
\end{center}
However, this is not the only way to draw our graph!  Another equally valid drawing is presented here:
\begin{center}
\includegraphics[width=1in]{mc2011_introgt_pentagon2.pdf}
\end{center}
\end{exmp}

Notice that this graph $G$ is planar, even though the second way we drew it had crossings: this is because there was \textbf{some} way to draw it without crossings!

\begin{defn}
A \textbf{face} of a planar graph $G$ is any region of the plane bounded by the edges of $G$.
\end{defn}

Here is a planar graph with all six of its faces labeled.  Notice how we count the ``outside'' face $f_6$ as a face: this is because you can think of the ``outside'' of this graph as something that's bounded\footnote{A joke that might help this make sense:  An engineer, a physicist, and a mathematician are shown a pasture with a herd of sheep, and told to put them inside the smallest possible amount of fence.

The engineer is first. He herds the sheep into a circle and then puts the fence around them, declaring, "A circle will use the least fence for a given area, so this is the best solution."

The physicist is next. He creates a circular fence of infinite radius around the sheep, and then draws the fence tight around the herd, declaring, "This will give the smallest circular fence around the herd."

The mathematician is last. After giving the problem a little thought, he puts a small fence around himself and then declares, "I define myself to be on the outside."} by the edges going around the boundary of this graph!
\begin{center}
\includegraphics[width=2in]{planar1.pdf}
\end{center}

\begin{enumerate}
\item In this homework problem, you're going to try to prove Euler's characteristic: take any planar graph, and suppose that $|V|$ is the number of vertices, $|E|$ is the number of edges, and $|F|$ is the number of faces.  Specifically, you're going to do this by induction!  Try following the blueprint here:
\begin{enumerate}
\item First, draw three planar graphs, one on 6 vertices, one on 7 vertices, and one on 9 vertices.  Check that our formula works on those three graphs! \newpage
\item Now, we're going to prove our formula by \textbf{induction}: specifically, we're going to induct on the \textbf{number of vertices.}   Therefore, our first case is to study what happens in our simplest case: What do planar graphs look like when they have only one vertex?  Explain why they all look like the following types of graphs:
\begin{center}
\includegraphics[width=2in]{planar2.pdf}
\end{center}
Show that $V-E+F = 2$ for these one-vertex ``flower'' graphs.
\item Now, we do the second phase of an inductive proof: we show how to reduce larger cases to smaller cases!  To do this, consider the following operation, called \textbf{edge contraction}.  Take any edge with two distinct endpoints.  Delete this edge, and combine its two endpoints together: this gives us a new graph!  We draw examples of this process below: we start with a graph on six vertices, and contract one by one the edges labeled in red at each step.
\begin{center}
\includegraphics[width=5in]{planar3.pdf}
\end{center}

Explain why contracting an edge does not change $V-E+F$.  (When you contract an edge: what happens to the total number of vertices?  How about edges?  How about faces?)
\item Conclude that by induction, because you know $V-E+F = 2$ for one-vertex planar graphs and you know that you can ``contract'' larger planar graphs to one-vertex graphs without changing $V-E+F$, that $V-E+F= 2$ for all planar graphs.
\end{enumerate}
\end{enumerate}




\end{document}