<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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] &amp;. \ar@{-}[r] \ar@{-}[d] \ar@{-}[dl] &amp;. \ar@{-}[d]\\
.\ar@/_/@{-}[rr] &amp; . &amp;.}

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

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

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

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

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

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


\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] &amp;v_2 \ar@{-}[r] \ar@{-}[d] \ar@{-}[dl] &amp;
v_3 \ar@{-}[d]\\v_4\ar@/_/@{-}[rr] &amp; v_5 &amp; v_6} 
\hfil and\hfil\xymatrix{w_1 \ar@{-}[r] \ar@{-}[d] &amp;
w_2 \ar@{-}[r] \ar@{-}[d] &amp; w_3 \ar@{-}[d] \ar@{-}[dl]\\
w_4\ar@{-}[r] &amp; w_5 \ar@{-}[r] &amp; w_6} 

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

(c) \xymatrix{v_1 \ar@{-}[d] \ar@{-}[dr] &amp;v_2 \ar@{-}[dr] \ar@{-}[d] \ar@{-}[r] &amp;v_3 \ar@{-}[d]\\
v_4 \ar@{-}[r] \ar@{-}[d] \ar@{-}[dr] &amp;v_5 \ar@{-}[d] \ar@/^/@{-}[d] \ar@{-}[r] &amp;v_6\\
v_7 \ar@{-}[r] &amp;v_8}\hfil and\hfil\xymatrix{w_1 \ar@{-}[r] \ar@{-}[d] \ar@{-}[ddrr] &amp;
w_2 \ar@{-}[r] &amp; w_3\ar@{-}[d] \ar@{-}@/^1pc/[dd]\\w_4 \ar@{-}[rr] \ar@{-}[dr] \ar@{-}[d] 
&amp;&amp; w_5 \ar@{-}[d]\\w_6 \ar@{-}[r] &amp; w_7 \ar@{-}[r] \ar@/_/@{-}[r] &amp; 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] &amp;. \ar@{-}[dl] \ar@{-}[d] \ar@{-}[r] &amp; . 
\ar@{-}[dll] \ar@{-}[dl] \\ . \ar@{-}[r] &amp; 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}
</pre></body></html>