\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{5, Mon.}                    % !! start the paper

\begin{problem}
There is a party.  Some people shake hands an even number of times and
some shake an odd number of times.  Show that an even number of people
shake hands an odd number of times.

\solution{We can represent the party by a graph.  (Yeah, right.)  Each person is
represented by a vertex.  If two people shake hands, then there is an
edge between the corresponding vertices.  This reduces the problem to
the following theorem:

\begin{theorem}
In every graph, there are an even number of vertices of odd degree.
\end{theorem}

\begin{proof}
Partitioning the vertices into those of even degree and those of odd
degree, we know
\[
{\sum_{v \in V} d(v)}\ =
{{\sum_{d(v) \mbox{ {\scriptsize is odd}}} d(v)}\ +\
{\sum_{d(v) \mbox{ {\scriptsize is even}}} d(v)}}
\]
The value of the lefthand side of this equation is even, and the second
summand on the righthand side is even since it is entirely a sum of even
values.  So the first summand on the righthand side must also be even.
But since it is entirely a sum of odd values, it must must contain an even
number of terms.  That is, there must be an even number of vertices with
odd degree.
\end{proof}
}

\end{problem}


\begin{problem}
Define a {\em halfgraph} to be a graph with $2n$ vertices, all of degree
exactly $n$, for some $n \geq 1$.  Can a halfgraph have more than one
connected component?  If so, draw an example.  If not, explain why.

\solution{No.  If the graph has two or more connected components, then
some connected component must have $n$ or fewer vertices.  (Otherwise,
there would be more than $2n$ vertices in all.)  Each vertex in this
component can have degree at most $n - 1$.}
\end{problem}


\begin{problem}
A set, $M$, of vertices of a graph is a \emph{maximal connected} set if
every pair of vertices in the set are connected, and any set of vertices
properly containing $M$ will contain two vertices that are not connected.

\bparts

\ppart What are the maximal connected subsets of the following
(unconnected) graph?

\mfigure{!}{1.5in}{figures/3comp}
\solution{
There are three maximal subsets, each one equal to the vertices of one of
the connected components of the graph.
}

\ppart Explain the connection between maximal connected sets and connected
components.

\solution{
They are the same.
}

\ppart Prove it.

\solution{
We first show that a connected component is a maximal set.  A connected
component consists of \emph{all} the vertices connected to some vertex
$v$.  A larger set of vertices would, by definition, contain both $v$ and
a vertex, $w$, that is not in the connected component.  This means that
$w$ is not connected to $v$, and therefore the larger set is not
connected.  So a connected component is maximal.

Conversely, suppose we have a maximal connected set, $M$.  Since $M$ 
connected, any vertex, $v$, in $M$ is connected to all the other vertices
in $M$.  If there was any vertex, $w$, connected to $v$, that was not in
$M$, then $M \union \set{w}$ would be connected and properly contain $M$,
contradicting the maximality of $M$.  So $M$ consists of exactly the
vertices connected to $v$, proving that it is a connected component.
}

\eparts
\end{problem}

\instatements{\newpage}

\begin{problem}
\bparts
\ppart Describe a connected graph such that every vertex is on a simple
cycle, but the graph is not 2-connected.

\solution{Two cycles connected by an edge.}

\ppart
Prove that a graph is 2-connected iff it is connected and every edge is
traversed by a simple cycle.
\solution{
To prove the iff from left to right, we assume some edge, $\edge{v}{w}$,
is not traversed by any simple cycle and then show that the graph is not
2-connected.

Now if there was a simple path between $v$ and $w$ that did not traverse
this edge, then this path together with the edge, would be a simple cycle
that traversed the edge.  So every simple path from $w$ to $v$ must
traverse this edge.  So if this edge is removed, no simple path will
connect $v$ and $w$, which implies that no path whatsoever connects them.
This proves the graph is not 2-connected.

Conversely, suppose the graph is connected but not 2-connected.  We will
show that edge is not on a simple cycle.

Since the graph is connected but not 2-connected, there must be a ``cut'
edge $\edge{v}{w}$ whose removal leaves a disconnected graph.  Now if
there was a simple cycle that traversed this edge, then the cycle minus
this edge would be a simple path, $P$, between $v$ and $w$ that did not
traverse the edge.  So any path connecting two points that traversed this
edge could be replaced by a path containing $P$ in place of the edge.
Therefore, all edges that were connected before the edge was removed would
still be connected after it is removed.  So since the original graph was
connected, it remains connected after the edge is removed.  This would
imply the graph was 2-connected, a contradiction.  So there cannot be a
simple cycle that traverses a cut edge.}
\eparts
\end{problem}

\begin{problem}
How many spanning trees does the following graph have?

\mfigure{!}{1.5in}{figures/spanning-tree}

\solution{There are a \textbf{lot} of possible spanning trees: David wrote
a computer program to solve the problem and found a total of 115 spanning
trees.

So we didn't expect any teams to completely solve this problem.  However,
we did expect teams to start generating spanning trees and also to
consider how to determine when they had them all.

There are efficient algorithms for counting spanning trees in arbitrary
graphs, but they typically involve complex procedures like computing
matrix determinants, which is tricky to do efficiently.  For this
particular problem, a more straighforward approach is to use a combination
of brute force and case analysis, which is feasible, if tedious, to work
out by hand.}

\end{problem}
\end{document} 
