\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 11}{Due: Nov. 5, 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 Let $G$ be the following graph.
\begin{center}
\begin{tikzpicture}[yscale=0.5,xscale=0.8]
	\tikzstyle{vertex}=[circle,draw]
	\node[vertex] at (-1,-1) (U1) {$u_1$} ;
	\node[vertex] at (5,-1) (U2) {$u_2$} ;
	\node[vertex] at (5,5) (U3) {$u_3$} ;
	\node[vertex] at (-1,5) (U4) {$u_4$} ;
	\node[vertex] at (1,1) (U5) {$u_5$} ;
	\node[vertex] at (3,1) (U6) {$u_6$} ;
	\node[vertex] at (3,3) (U7) {$u_7$} ;
	\node[vertex] at (1,3) (U8) {$u_8$} ;
	
	\draw (U1) -- (U2) -- (U3) -- (U4) -- (U8) -- (U7) -- (U6) -- (U5) -- (U1) -- (U4) (U5) -- (U8)  (U7) -- (U3) (U2) -- (U6) ;
	
\end{tikzpicture}
\end{center}
\begin{enumerate}
	\item How many $4$-cycles are in $G$?
	\item How many $8$-cycles are in $G$?  Draw them all.  Hint: there are the same number of $4$-cycles as $8$-cycles.
	\item Find an induced $6$-cycle in $G$.
\end{enumerate}

\item Let $m\ge 2$.  How many paths on $m$ vertices does $K_n$ contain?  

\item Let $G$ be the graph whose vertices are the subsets of $\{1,2,3,4,5\}$ of size 2 with two vertices adjacent if and only if they are disjoint.  For example, $V(G) = \{\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \ldots, \{4,5\}\}$; we have that $\{1,2\}$ and $\{1,4\}$ are not adjacent, but $\{1,2\}$ and $\{3,5\}$ are adjacent.  Show that $G$ is the Petersen graph.

\item Decide whether the following pairs of graphs are isomorphic.  If they are isomorphic, give the function that establishes the isomorphism.  If not, explain why.
\begin{enumerate}
	\item 
		\begin{tikzpicture}[every node/.style={vertex},baseline=0,scale=0.8]
			\begin{scope}[shift={(-4,0)}]
				\foreach \x/\y/\n in {1/0/a, 0/1/b, -1/0/c, 0/-1/d}
				{
					\node at (\x,\y) (\n) {\n} ;
				}
				\draw (a) -- (b) -- (c) -- (d) -- (a) -- (c) ;
			\end{scope}
			\begin{scope}[shift={(4,0)}]
				\foreach \x/\y/\n in {1/0/1, 0/1/2, -1/0/3, 0/-1/4}
				{
					\node at (\x,\y) (\n) {\n} ;
				}
				\draw (1) -- (2) -- (3) -- (4) -- (1)  ;
				\draw (2) -- (4) ;
			\end{scope}
		\end{tikzpicture}
		\vfill

	\item 
		\begin{tikzpicture}[every node/.style={vertex},baseline=0,scale=0.8]
			\begin{scope}[shift={(-4,0)}]
				\foreach \x/\n in {-2/a, 0/b, 2/c}
				{
					\node at (\x,1) (\n) {\n} ;
				}
				\foreach \x/\n in {-2/d, 0/e, 2/f}
				{
					\node at (\x,-1) (\n) {\n} ;
				}
				\draw (a) -- (b) -- (c) -- (d) -- (e) -- (f) -- (a) ;
				\draw (d) -- (b) -- (f) ;
				\draw (a) -- (e) -- (c) ;
			\end{scope}
			\begin{scope}[shift={(4,0)}]
				\foreach \x/\y/\n in {-2/1/1, 2/1/2, -2/-1/3, 2/-1/4, 0/0.5/5, 0/-0.5/6}
				{
					\node at (\x,\y) (\n) {\n} ;
				}
				\draw (1) -- (3) (2) -- (4) ;
				\draw (1) -- (5) -- (4) -- (6) -- (1) ;
				\draw (2) -- (6) -- (3) -- (5) -- (2) ;
			\end{scope}
		\end{tikzpicture}
		\vfill
	\item 
		\begin{tikzpicture}[every node/.style={vertex},baseline=0,scale=0.8]
			\begin{scope}[shift={(-4,0)}]
				\foreach \x/\n in {0/a,45/b,90/c,135/d,180/e,225/f,270/g,315/h}
				{
					\node at (\x:2cm) (\n) {\n} ;
				}
				%\draw (a) -- (b) -- (c) -- (d) -- (e) -- (f) -- (g) -- (h) -- (a) ;
				\draw (a) -- (e) (b) -- (f) (c) -- (g) (d) -- (h) ;
				\draw (a) -- (d) -- (g) -- (b) -- (e) -- (h) -- (c) -- (f) -- (a) ;
			\end{scope}
			\begin{scope}[shift={(4,0)}]
				\foreach \x/\n in {0/1,45/2,90/3,135/4,180/5,225/6,270/7,315/8}
				{
					\node at (\x:2cm) (\n) {\n} ;
				}
				%\draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (1) ;
				\draw (1) -- (5) (2) -- (6) (3) -- (7) (4) -- (8) ;
				\draw (1) -- (3) -- (5) -- (7) -- (1)  ;
				\draw (2) -- (4) -- (6) -- (8) -- (2) ;
			\end{scope}
		\end{tikzpicture}
		\vfill
\end{enumerate}

\end{enumerate}

\end{document}
