\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{16: Toroidal Graphs}{Due Friday, week 10}


Pick \textbf{three} of the problems in this set to solve!  Solutions need justification and proof to receive full credit: i.e.\ it is not enough to simply draw the answer.  

\begin{enumerate}
\item In class, we created a way to glue together sides of a square to make a torus:
\begin{center}
\includegraphics[width=4in]{math137b_s2014_torus.pdf}
\end{center}
 The picture below shows how to glue together sides of an octagon to create a ``two-hole torus:''
\begin{center}
\includegraphics[width=5in]{math137b_s2014_twotorus.pdf}
\end{center}
\begin{enumerate}
\item Create a way to glue together the sides of a square to get a sphere.
\item Create a way to glue together the sides of a $4n$-gon to get a $n$-hole torus.
\item Create a way to glue together the opposite sides of a hexagon to get a torus.
\end{enumerate}
\item A graph $G$ drawn on a $n$-hole torus is called $n$-\textbf{toroidal} if it satisfies the same definition we gave in class (i.e. we can draw it on a $n$-hole torus so that no edges intersect and the regions bounded by edges look like open regions of $\mathbb{R}^2$.)  
\begin{enumerate}
\item Prove that if $G$ is a $2$-toroidal graph, then $V-E+F = -2$.
\item Generalize the above problem: show that if $G$ is an $n$-toroidal graph, then $V-E+F = 2-2n$.
\end{enumerate}
\item Suppose that $G$ is planar.  Prove that there is a planar embedding of $G$ in the plane where all of the edges are drawn with straight line segments.  

\item \begin{enumerate}
\item Show that there is no connected bipartite 3-regular planar graph on 10 vertices.
\item Show that for any even $n \geq 4, n \neq 5$, there is a connected bipartite 3-regular planar graph on $2n$ vertices.
\end{enumerate}
\item In class we proved Heawood's formula, which in the case where $g=0$ is the four-color theorem!  Explain why our proof fails for $g=0$.
\end{enumerate}



\end{document}