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

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 13}{Due: Dec. 8, 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.

\newcommand{\withextraedges}[1]
{
	%\begin{center}
	\begin{tikzpicture}[scale=1]
	\tikzstyle{vertex}=[circle,draw,fill=black!20,inner sep=0pt, minimum size=1ex]
	\begin{scope}[every node/.style={vertex}]
		\foreach \x in {1,2,3}
		{{
			\foreach \y in {1,2,3}
			{{
				\node at (\x,\y) (U\x\y) {} ;
			}}
		}}
	\end{scope}
	
	\foreach \a in {1,2,3}
	{{
		\foreach \b in {1,2}
		{{
			\draw let \n{succ}={int(\b+1)} in (U\a\b) -- (U\a\n{succ}) (U\b\a) -- (U\n{succ}\a) ;
		}}
	}}
	
	\foreach \a/\b/\c/\d/\style in {#1}
	{{
		\draw (U\a\b) edge[\style] (U\c\d) ;
	}}
	
	\end{tikzpicture}
	%\end{center}
}


\begin{enumerate}

\item For each of the following graphs, either give a planar drawing or show that the graph contains a subdivision of $K_5$ or $K_{3,3}$.
\begin{multicols}{3}
\begin{enumerate}
\item ~\\ \withextraedges{2/1/2/3/bend left,1/2/3/2/bend left}
\item ~\\ \withextraedges{2/1/2/3/bend left,1/1/3/1/bend left}
\item ~\\ \withextraedges{2/1/2/3/bend left,3/1/3/3/bend left}
\end{enumerate}
\end{multicols}

\item Suppose that a connected $k$-regular planar graph $G$ is drawn so that every face has length $\ell$.  Find a formula for the number of faces of $G$ in terms of $k$ and $\ell$.

\item Find all perfect matchings in the cube.  How many are there?
\begin{center}
\begin{tikzpicture}[scale=0.5]
	\tikzstyle{vertex}=[circle,draw,fill=black!20,inner sep=0pt, minimum size=1ex]
	\node[vertex] at (-1,-1) (U1) {} ;
	\node[vertex] at (5,-1) (U2) {} ;
	\node[vertex] at (5,5) (U3) {} ;
	\node[vertex] at (-1,5) (U4) {} ;
	\node[vertex] at (1,1) (U5) {} ;
	\node[vertex] at (3,1) (U6) {} ;
	\node[vertex] at (3,3) (U7) {} ;
	\node[vertex] at (1,3) (U8) {} ;
	
	\draw (U1) -- (U2) -- (U3) -- (U4) -- (U8) -- (U7) -- (U6) -- (U5) -- (U1) -- (U4) (U5) -- (U8)  (U7) -- (U3) (U2) -- (U6) ;
\end{tikzpicture}
\end{center}

\newcommand{\bigraph}
{
	\tikzstyle{vertex}=[circle,draw,fill=black!20,inner sep=0pt, minimum size=1ex]

	\begin{scope}[xscale=1.2,yscale=-1.50,every node/.style={vertex}]
		\foreach \i in {1, ..., 7}
		{
			\node at (-1,\i) (X\i) {} ;
			\node at (1,\i) (Y\i) {} ;
		}
	\end{scope}

	\path (X7) +(0,-3ex) node[anchor=north] {$X$} ;
	\path (Y7) +(0,-3ex) node[anchor=north] {$Y$} ;


	\foreach \i/\j in {1/1,1/2,2/1,2/2,2/3,3/2,3/4,4/3,4/4,5/3,5/4,6/4,6/5,6/6,6/7,7/5,7/6,7/7}
	{
		\draw (X\i) -- (Y\j) ;
	}
}

\item Find a maximum matching in the following bipartite graph and a set $S\subseteq X$ whose deficiency proves the matching is maximal.
\begin{center}
\begin{tikzpicture}[scale=0.75]
	\bigraph
\end{tikzpicture}
\end{center}


\end{enumerate}

\end{document}
