\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 12}{Due: Nov. 19, 2015}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  \textbf{Show your work}; See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Show that when any edge is removed from $K_5$, the resulting subgraph is planar.  Is this true for $K_{3,3}$?

\item Let $G$ be a connected planar graph (without loops or parallel edges).  One way of embedding $G$ in the plane creates 53 regions, each of which has at least five edges on its boundary.  Prove that $G$ has at least 82 vertices.

\item Let $G$ be a connected planar graph (without loops or parallel edges). 
\begin{enumerate}
	\item The complement of $G$, denoted $\overline{G}$, is the graph on $V(G)$ where $u$ and $v$ are adjacent in $\overline{G}$ if and only if they are non-adjacent in $G$.  Prove that if $|V(G)| \ge 11$, then $G$ or $\overline{G}$ is nonplanar.  Hint: count edges in $G$ and $\overline{G}$.
	
	\item Find an $8$-vertex graph $G$ such that $G$ and $\overline{G}$ are planar.
\end{enumerate}

\end{enumerate}

\end{document}
