\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 8

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

\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] Find minimal spanning trees for the following graphs:

(a) \xymatrix{. \ar@{-}[r]^{15} \ar@{-}[d]_{12} &. \ar@{-}[r]^{7} \ar@{-}[dr]_{2} 
\ar@{-}[dl]^{9} &. \ar@{-}[d]^{11}\\
.\ar@{-}[rr]_8 & . &.}

(b) \xymatrix{. \ar@{-}[r]^{4} \ar@{-}[d]_{8} \ar@{-}[ddr]_{14} &. \ar@{-}[dr]^{8} \ar@{-}[dd]_{6} &. 
\ar@{-}[d]^{3}\\
. \ar@{-}[d]_{6} &  &. \ar@{-}[dl]^{7} \\. \ar@{-}[r]_{5}&.}

%(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] How many spanning trees are there for the following graph?

\hfil\xymatrix{&. \ar@{-}[dr] \ar@{-}[dl] & &. \ar@{-}[dr] \ar@{-}[dl] & &. \ar@{-}[dl] 
\ar@{-}[dd]\\
.\ar@{-}[d] & & . \ar@{-}[dl] \ar@{-}[dr] &&. \ar@{-}[dl] \ar@{-}[dr]\\
.\ar@{-}[r] &.&&.&&.}

\item[3] (a) What is the minimum number of cycles that a graph with 5 vertices and 6 
edges can have? Justify your answer.

(b) Draw a graph with 5 vertices, 6 edges and the number of cycles in your answer to (a). 
[Careful -- it's easy to draw a graph with too many cycles.]

\item[4] 

(a)  How many trees are needed to cover all the edges of $K_5$ (the complete graph on 
5 vertices)? i.e. we want a collection of trees with vertices chosen from the vertices of 
our $K_5$, such that the union of their edges is the collection of all edges of the $K_5$. 
Justify your answer.

(b) Draw a collection of this many trees that cover the edges of the $K_5$.

\item[5] Let $T$ be a tree with $n\geqslant 3$ vertices. Let $G$ be a graph obtained by 
adding one new edge to $T$. Show that $G$ contains exactly one cycle.

\end{list}

\end{document}
