\documentclass{article}
\usepackage{amssymb,graphics}
\input xy
\xyoption{all}

\def\mod#1{\ ({\rm mod\ }#1)}

\begin{document}
\begin{center}
{\Large
MATH 2113/CSCI 2113, Discrete Structures II

Winter 2008

Toby Kenney

\large Homework Sheet 7

Due: Wednesday 19th March: 1:30 PM}
\end{center}

\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] Which of the following graphs have Euler circuits?

(a) \xymatrix{. \ar@{-}[r] \ar@{-}[dr] &. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dl] &. \ar@{-}[d]\\
.\ar@/_/@{-}[rr] & . &.}

(b) \xymatrix{. \ar@{-}[r] \ar@{-}[dd] &. \ar@{-}[dr] \ar@{-}[dd] &. \ar@{-}[ddll]\\
&  &.\\.&.}

(c) \xymatrix{. \ar@{-}[d] \ar@{-}[dr] &. \ar@{-}[dr] \ar@{-}[d] \ar@{-}[r] &. \ar@{-}[d]\\
. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &. \ar@{-}[d] \ar@/^/@{-}[d] \ar@{-}[r] &.\\. \ar@{-}[r] &.}

\item[2] Find Hamiltonian circuits in the following graphs.

(a) \xymatrix{. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dl] &. \ar@{-}[d]\\
.\ar@/_/@{-}[rr] & . &.}

(b) \xymatrix{. \ar@{-}[r] \ar@/_/@{-}[dd] \ar@{-}[d]&. \ar@{-}[dr] \ar@{-}[dd] \ar@{-}[dl] 
&. \ar@{-}[ddll] \ar@{-}[ddl] \\
. \ar@{-}[rr] &  &.\\.&.}

(c) \xymatrix{. \ar@{-}[d] \ar@{-}[dr] &. \ar@{-}[dr] \ar@{-}[d] \ar@{-}[r] &. \ar@{-}[d]\\
. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &. \ar@{-}[d] \ar@{-}[r] &.\ar@{-}[dll]\\. \ar@{-}[r] &.}


\item[3] (a) Draw a simple graph with vertices of degrees 2,2,3,3,4,5,6,6,7.

(b) Is there a simple graph with vertices of degrees 2,3,4,5,6,6,6,6,7?

\item[4] Which of the following pairs of graphs are isomorphic? For pairs which are 
isomorphic, write down the isomorphism. For pairs which are not isomorphic, give a 
reason why they are not isomorphic.

(a)  \xymatrix{v_1 \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &v_2 \ar@{-}[r] \ar@{-}[d] \ar@{-}[dl] &
v_3 \ar@{-}[d]\\v_4\ar@/_/@{-}[rr] & v_5 & v_6} 
\hfil and\hfil\xymatrix{w_1 \ar@{-}[r] \ar@{-}[d] &
w_2 \ar@{-}[r] \ar@{-}[d] & w_3 \ar@{-}[d] \ar@{-}[dl]\\
w_4\ar@{-}[r] & w_5 \ar@{-}[r] & w_6} 

(b)\xymatrix{v_1 \ar@{-}[r] \ar@{-}[dd] &v_2 \ar@{-}[dr] \ar@{-}[dd] &v_3 \ar@{-}[ddll]\\
&  &v_4\\v_5&v_6} \hfil and\hfil
\xymatrix{w_1 \ar@{-}[r] \ar@{-}[dr] & w_2 \ar@{-}[d] & w_3 \ar@{-}[dl] \\
w_4 \ar@{-}[r]&w_5 \ar@{-}[d]\\&w_6}

(c) \xymatrix{v_1 \ar@{-}[d] \ar@{-}[dr] &v_2 \ar@{-}[dr] \ar@{-}[d] \ar@{-}[r] &v_3 \ar@{-}[d]\\
v_4 \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &v_5 \ar@{-}[d] \ar@/^/@{-}[d] \ar@{-}[r] &v_6\\
v_7 \ar@{-}[r] &v_8}\hfil and\hfil\xymatrix{w_1 \ar@{-}[r] \ar@{-}[d] \ar@{-}[ddrr] &
w_2 \ar@{-}[r] & w_3\ar@{-}[d] \ar@{-}@/^1pc/[dd]\\w_4 \ar@{-}[rr] \ar@{-}[dr] \ar@{-}[d] 
&& w_5 \ar@{-}[d]\\w_6 \ar@{-}[r] & w_7 \ar@{-}[r] \ar@/_/@{-}[r] & w_8}

\item[5] Write down the adjacency matrix for the following graph. How many cycles of 
length 3 are there that pass through the vertex $v$?

\hfil\xymatrix{. \ar@{-}[r] \ar@/^/@{-}[r] &. \ar@{-}[dl] \ar@{-}[d] \ar@{-}[r] & . 
\ar@{-}[dll] \ar@{-}[dl] \\ . \ar@{-}[r] & v}

\item[6] For which values of $m$ and $n$ does the complete bipartite graph on $m$ and 
$n$ vertices have a Hamiltonian cycle? Justify your answer.

\end{list}

\end{document}
