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


Pick \textbf{one} 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.

Also, in class I mentioned that I would have a problem describing the torus here.  I decided that this was something better done in class, so look for this there!

\begin{enumerate}
\item Let $G$ be a planar $n$-vertex graph with girth $k$ (i.e.\ a graph that contains a $k$-cycle as a subgraph, but no smaller cycles as subgraphs.)
\begin{enumerate}
\item Prove that $G$ has at most $(n-2)\frac{k}{k-2}$ edges.
\item Explain why this means the Petersen graph is nonplanar.
\end{enumerate}
\item \begin{enumerate}
\item Show that if $G$ is a planar graph on 11 vertices, then the complement of $G$ is nonplanar.
\item Find a planar graph $G$ on 8 vertices such that its complement is planar.
\end{enumerate}
\end{enumerate}



\end{document}