\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{\vspace*{0.5in}}
\fi
\typeout{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut4}
\newcommand{\tutnum}{4}
\newcommand{\tutdate}{February 25, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item Construct the adjacency matrix that represents the following graph.

\medskip

\centerline{\psfig{figure=figures/mq4p1.eps,height=1.3in}}

\omitsolution{%
  \begin{solution}
    
  \end{solution}
  }

\end{enumerate}

\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem %
Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends.

\bparts
\ppart

Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.  \hint See part (d).

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\omitsolution{%
  \begin{solution}
\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}
\end{center}
\centerline{The smallest two-ended graph not isomorphic to any line graph.}
\end{figure}
  \end{solution}
  }

\ppart
Explain briefly, but clearly, what is wrong with the following
argument:

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n~\ge~1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.


\omitsolution{%
\begin{solution}

The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).  

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.

  \end{solution}%
  }


\ppart
Here is another argument for the same False Theorem as in part~(b).
Explain exactly where it goes wrong.

\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.

\omitsolution{%
\begin{solution}

The claim
\begin{quotation}\noindent
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.
\end{quotation}
is wrong.  The degree of $w$ is one less
in~$G_n$ than it was in~$G_{n+1}$, hence it can be equal to one if it
was two in $G_{n+1}$, but it can also be equal to zero if it was one
in $G_{n+1}$.  The false proof above is wrong because it ignores this
this second possibility.  For example, if we take $G_{n+1}=G_4$ from
the solution to part (a):
\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(00,20){w}
\put(20,20){v}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}
\end{center}
\centerline{Graph $G_{n+1}$}
\end{figure}

We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}}
\put(00,20){w}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}
\end{center}
\centerline{Graph $G_{n}$}
\end{figure}

Obviously, $G_n$ is not a line graph.
  \end{solution}%
  }


\ppart
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\omitsolution{%
\begin{solution}

The proof in part (c) can be easily fixed if the graphs are connected,
because then the quoted false claim will be true.  Here is an
example of how one could inject into the proof from part (c) an
argument justifying the claim for the case of connected
graphs:
\begin{quotation}
[...But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$.]
Since $G_{n+1}$ was two-ended, $w$ must be of degree either one or two
in $G_{n+1}$.  However, it cannot be of degree one because then
vertices $v$ and $w$ would be connected only to each other and
disconnected from the rest of the graph, which would contradict the
assumption that $G_{n+1}$ is connected.  Therefore, $w$ must have
degree two in $G_{n+1}$, and hence has degree one in $G_n$.
Hence, [ $G_n$ still has two vertices of degree~one and one fewer
vertex of degree~two.  Therefore...]
\end{quotation}

The false proof in part (b) cannot be easily fixed.  If we tried to
use its structure to prove that all connected two-ended graphs are
linear graphs, we would have to supply the argument that every
connected two-ended graph can be formed by adding an edge to some
connected two-ended graph with one less edge.  To argue that would be
as complicated as the above proof.
  \end{solution}%
  }



\eparts

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage %
\problem %
Over the weekend, your 6.042 TAs came across the following puzzle: a
$3 \times 3$ grid of squares, where each square contains one of the
digits in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$, each digit
appearing exactly once in the puzzle.  Each row can be rotated right
or left and each column can be rotated up or down.  The effects of
such rotations are demonstrated in the following figure.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode

\[
\begin{array}{|c|c|c|}
\hline
2 & 3 & 6 \\ \hline
7 & 8 & 9 \\ \hline
5 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
2 & 8 & 9 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
8 & 9 & 2 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\]

  \end{center}
  \caption{Examples of puzzle row and column rotations.}
  \label{fig:roteg}
\end{figure}

The first picture shows the initial configuration of the puzzle.  The
leftmost column is then rotated downward to give the middle picture.
The $2$ and $7$ move down and the $5$ rotates back up to the top.
Then, the middle row is rotated leftward to produce the final picture.
The $8$ and $9$ move left and the $2$ rotates back around to the
right.

Since discovering the puzzle, your 6.042 TAs have spent hours trying
to obtain the following configuration, starting of course from the
initial configuration of Figure~\ref{fig:roteg} and using legal row
and column rotations.

\[
\begin{array}{|c|c|c|}
\hline
1 & 2 & 3 \\ \hline
4 & 5 & 6 \\ \hline
7 & 8 & 9 \\ \hline
\end{array}
\]

Sad to say, your 6.042 TAs have failed miserably.

Based on prior experience with puzzles, the 6.042 students believe
that the puzzle might be designed in a way that makes this
configuration impossible, no matter what sequence of row and column
rotations one attempts.

\begin{problemparts}

  \problempart Model the puzzle as a state machine.

\omitsolution{%
\begin{solution}

The puzzle can be modeled by the state machine $M$ defined as follows:

\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the digits
  in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$ on a $3 \times 3$ grid
  where each digit appears exactly once.

\item The set of start states $Q_0$ consists of the single arrangement
  236 789 541.

\item The set $\delta \subseteq Q \times Q$ consists of all pairs of
  states $(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a
  row or column rotation.

\end{itemize}
  \end{solution}%
  }

\problempart Given the initial configuration of the puzzle indicated
above, namely 236 789 541, prove that your 6.042 TAs can never obtain
the configuration 123 456 789.

\omitsolution{%
\begin{solution}

  The idea is to keep track of the number of digit pairs that are out
  of order relative to the desired configuration 123 456 789.  For
  example, in the initial configuration, $2$ appears before $1$; this
  pair of digits is out of order, because $1$ appears before $2$ in
  the desired configuration 123 456 789.  We will refer to an
  out-of-order digit pair as an {\em inversion}.  In the initial
  configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
21 & 31 & 61 & 64 & 61 \\
75 & 74 & 71 & 85 & 84 \\
81 & 95 & 94 & 91 & 54 \\
51 & 41
\end{array}
\]

The key observation is that a rotation always changes the number of
inversions by an even amount.  Since the puzzle initially has an odd
number of inversions, no sequence of rotations can reduce the number
of inversions to 0, an even number.  Consequently, there will always
be at least one pair of digits out of order.

The main challenge is to prove that a rotation always changes the
number of inversions by an even amount.  We will prove this claim in a
sequence of lemmas, and then we will prove the main result as a
theorem.

\begin{lemma}
Swapping an adjacent pair of digits changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
  If the digits were initially in the same order as in 123 456 789,
  then the number of inversions is increased by 1, an odd number.
  Otherwise, the digits were initially in the wrong order, and the
  number of inversions is decreased by 1, also an odd number.
\end{proof}

\begin{lemma}
Swapping any pair of digits changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
  We will show how to swap any pair of digits using an odd number of
  swaps of adjacent digits.  The preceding lemma says that swapping
  adjacent digits changes the number of inversions by an odd amount.
  Therefore, swapping any pair of digits changes the number of
  inversions by an odd amount, because the sum of an odd number of odd
  numbers is odd.

  All that remains is to show how to swap any pair of digits using an
  odd number of swaps of adjacent digits.  Suppose that we are
  swapping digits $x$ and $y$, where $x$ is on the left, $y$ is on the
  right, and there are $k$ stray digits between the two.  First, we
  swap $x$ with its right neighbor $k$ times.  This leaves $x$
  directly left of $y$ and leaves all the stray digits shifted one
  place to the left.  Then we swap $x$ and $y$, putting $x$ into $y$'s
  original positions.  Finally, we swap $y$ with its left neighbor $k$
  times.  This puts $y$ into $x$'s original position and shifts the
  stray digits back to their original position.  The total number of
  swaps of adjacent digits is $k + 1 + k = 2k + 1$, which is odd for
  all $k \geq 0$.
\end{proof}

\begin{lemma}\label{lem:rotate}
  Rotating any row or column changes the number of inversions by an
  even amount.
\end{lemma}

\begin{proof}
  We show below that any row or column rotation can be obtained by two
  swaps.  The preceding lemma says that every swap changes the number
  of inversions by an even amount.  Since the sum of two odd numbers
  is even, any row or column rotation changes the number of inversions
  by an even amount.

  Here is how to obtain a rotation from two swaps.  Suppose that the
  digit sequence $xyz$ appears in some row or column.  Swapping $x$
  with $y$ and then swapping $x$ with $z$ creates the sequence $yzx$,
  which corresponds to a leftward or upward rotation.  Swapping $z$
  with $y$ and then $z$ with $x$ creates the sequence $zxy$.  This
  corresponds to a rightward or downward rotation.
\end{proof}

\begin{theorem}
  Your 6.042 TAs can not obtain the configuration 123 456 789.
\end{theorem}

\begin{proof}
  Let $P$ be a predicate on the states of $M$, denoting whether the
  number of inversions in the digit sequence of the puzzle relative to
  the 123 456 789 sequence is odd.  Moreover, let $P'(n)$, for $n \geq
  0$, be the predicate that asserts $P$ for all states that can be
  reached by $n$-step executions of $M$.  We show that $P$ is an
  invariant property of $M$, by showing that $P'(n)$ holds for all
  $n\geq0$.  The proof is by induction on the length $n$ of the
  execution of the state machine $M$.

  For the base case, we need to show that the property holds in the
  start state, \ie an execution of length $n = 0$.  This is true
  because in the initial configuration, the number of inversions is
  odd, in particular equal to 17.  For the inductive step, we must
  show that if $P$ holds for any configuration reachable after $n$
  steps of $M$, the $P$ holds for any configuration reachable after
  $n+1$ steps of $M$.  Fix $n \geq 0$ and let $q_0, q_1,\ldots, q_n,
  q_{n+1}$ denote any $n+1$-step execution of $M$.  $q_n$ is thus the
  final state of an $n$-step execution of $M$.  Thus, by our inductive
  hypothesis, in the state $q_n$, the puzzle has an odd number of
  inversions.  Now, consider the final step $(q_n,q_{n+1})$ of the
  $n+1$-step execution of $M$.  By Lemma~\ref{lem:rotate}, this step
  changes the number of rotations by an even amount.  It follows that
  the number of rotations of the state $q_{n+1}$ is odd.  Thus, by
  induction, we have shown that $P$ is an invariant property of $M$.

  Finally, since the number of inversions relative to 123 456 789 is
  always odd, the desired configuration with 0 inversions can not be
  obtained.
\end{proof}

In the above proof, we have proven that the the property that the
puzzle has an odd number of inversions is an invariant property of the
state machine $M$.

The following theorem, denoted the \emph{invariant theorem}, is a
generic theorem that specifies what an property of a state machine
must satisfy in order for the property to be an invariant.  The
following presentation and proof of the theorem is taken directly from
Nancy's notes on computational processes, installment 2.

\begin{theorem}
(Invariant theorem) \\
Suppose $M = (Q,Q_0,\delta)$ is a state machine, and $P$ is a
predicate of states in $Q$ such that: 
\begin{enumerate}
\item
$\forall q \in Q_0  (P(q))$, and
\item
$\forall (q,q') \in \delta (P(q) \Rightarrow P(q'))$.
\end{enumerate}
Then $P$ is an invariant of $M$ (that is, is true in all reachable
states of $M$). 
\end{theorem}

\begin{proof}
Prove this using ordinary induction, on the number of steps in the
execution: \\
First formulate a new predicate $P'(n)$ that asserts $P$ for all the states
that can be reached by $n$-step executions. \\
Prove $P'$ using ordinary induction on $n$. \\
\\
The base step, $P'(0)$, says that $P$ is true of all states that occur in
$0$-step executions, that is, the start states. \\
That follows easily by assumption.\\
The inductive step takes a little more work, but basically follows
from the second assumption.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Given: $M = (Q,Q_0,\delta)$ is a state machine. \\
Given: $\forall q \in Q_0  (P(q))$ \\
Given: $\forall (q,q') \in \delta (P(q) \Rightarrow P(q'))$. \\
Prove: $P$ is an invariant of $M$, that is,
$\forall q \in Q (q \mbox{ reachable } \Rightarrow P(q))$ \\
1. $\forall n \geq 0 (P'(n))$, where $P'(n)$ is the predicate
   $\forall q$, a final state of an $n$-step execution $(P(q))$. \\
\> 1. (Base) $P'(0)$ 
   \> \> \> \> By the assumption about start states \\
\> 2. (Inductive step) $\forall n \geq 0 (P'(n) \Rightarrow P'(n+1))$ \\
\> \> 1. Fix $n \geq 0$ \\
\> \> 2. Assume $P'(n)$ \\
\> \> 3. $P'(n+1)$ 
      \> \> \> ??? \\
\> \> 4. QED \\
\> 3. QED
   \> \> \> \> Induction \\
2. QED
\> \> \> \> \> Definition of ``reachable''
\end{tabbing}

Expanding the inductive step shows how the second assumption is
used. \\
Namely, we consider the final state of any $n+1$-step execution, in
order to show that $P$ holds there. \\
We see that this arises from the final state of an $n$-step execution,
via one more step. \\
But the state after the $n$-step execution satisfies $P$, by inductive
hypothesis. \\
And the last step preserves $P$, by assumption. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 3. $P'(n+1)$, that is, $P$ is true for all final states of $n+1$-step
executions. \\
\> \> \> 1. Fix an $n+1$-step execution $q_0,q_1,\ldots,q_n,q_{n+1}$. \\
\> \> \> 2. $q_n$ is the final state of an $n$-step execution. \\
\> \> \> 3. $P(q_n)$ 
         \> \> Inductive hypothesis (1.2.2) \\
\> \> \> 4. $(q_n,q_{n+1})$ is a step of $M$. \\
\> \> \> 5. $P(q_{n+1})$ 
         \> \> By the assumption about steps preserving $P$ \\
\> \> \> 6. QED
         \> \> UG
\end{tabbing}

This proof may look a little confusing because there are {\em two\/}
predicates involved, $P$ and $P'$.  \\
Just remember that $P$ is a predicate about states, while $P'$ is a
predicate about numbers (lengths of executions). 
\end{proof}

\end{solution}%
}

\end{problemparts}

\end{document}

\endinput

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage %
\problem %
The \emph{rooted Fibonacci trees} $T_n$ are defined recursively in the
following way.  $T_1$ and $T_2$ are both the rooted tree consisting of
a single vertex, and for $n = 3, 4, \ldots$, the rooted tree $T_n$ is
constructed from a root with $T_{n-1}$ as it left subtree and
$T_{n-2}$ as its right subtree.

\problempart Draw the first seven rooted Fibonacci trees.

\omitsolution{%
  \begin{solution}
    
  \end{solution}
  }

\problempart How many vertices, leaves, and internal vertices does the
rooted Fibonacci tree $T_n$ have, where $n$ is a positive integer?
What is its height?
  
\omitsolution{%
  \begin{solution}
    
  \end{solution}
  }

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem %
The weighted graph in Figure~\ref{fig:flowprob} represents a system of
pipes.  The weight on an edge indicates the \emph{capacity} of the
corresponding pipe, that is, the maximum rate at which water can pass
through the pipe in gallons per second.  Suppose that water enters the
system at vertex $S$ and leaves the system at vertex $T$.  The goal of
this problem is to determine the \emph{capacity} of the system, that
is, the maximum rate at which water can pass through the entire system
in gallons per second.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/flowprob.eps,height=2in}}
%\vspace{2in}
\caption{\em Connections and capacities of some pipes.}
\label{fig:flowprob}
\end{figure}

A \emph{flow} is modeled by assigning to each edge a direction and a
nonnegative number, called the \emph{flow rate through the edge}.  The
\emph{flow rate out of a vertex} is the sum of the flow rates of edges
with flows directed out of the vertex; the flow rate \emph{into} a vertex
is defined similarly.  The \emph{net flow} out of a vertex is the
difference of the flow out of and the flow into the vertex.  The flow rate
of an edge must not exceed the capacity of the edge.  Also, except for the
vertices $S$ and $T$, the net flow out of each vertex must be zero.

\bparts

\ppart Prove that the net flow out of vertex $S$ equals the net flow into
$T$.  This number is called the \emph{overall rate} of the flow.

\omitsolution{%
  \begin{solution}
%

    The sum of the net flow rates out of all the vertices counts the
    flow on every edge once in each direction and therefore sums to
    zero.  Also, the net flow out of each vertex other than $S$ and
    $T$ is zero, so the net flow out of $S$ plus the net flow out of
    $T$ must also be zero.
  \end{solution}%
  }

\ppart The least upper bound of all possible overall flow rates is called
\emph{the capacity of the system}.

Define a flow for the system in Figure~\ref{fig:flowprob} with as large an
overall flow rate as you can.  So the capacity of the system is at least
as large as this flow rate.

\omitsolution{%
  \begin{solution}
%

With the flow rates and directions shown in Figure~\ref{fig:flowsol}, the
rate of flow through the entire system is 7 gallons per second, so the
capacity of the system is at least this large.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/flowsol.eps,height=2in}}
%\vspace{2in}
\caption{\em The maximum flow through the pipes.}
\label{fig:flowsol}
\end{figure}
  \end{solution}%
  }

\ppart Find a set of pipes with minimum total capacity such that removing
those pipes from the system completely cuts off vertex $S$ from vertex
$T$.  Mark these pipes on your diagram.  If you've done it right, this
total will equal the flow rate you found above.

\omitsolution{%
  \begin{solution}
%

The edges marked with X's in Figure~\ref{fig:flowsol} have a total
capacity of 7 gallons per second.  Removing these edges disconnects $S$
from $T$.
  \end{solution}%
  }

\ppart Explain why the capacity of a system can never exceed the capacity
of such a \emph{cut set} of edges cutting off $S$ from $T$.  (Don't offer
physical arguments about conservation of amount of liquid through pipes.
Such arguments \emph{assume} our model correctly reflects physical
reality, but that's exactly what we're trying to check.)  Conclude that
the capacity of the system is the rate you found in the two previous
parts.

\omitsolution{%
\begin{solution}
%
Let $L,R$ be any partition of the vertices into two sets with $S
\in L$ and $T \in R$, and consider some flow.  Define $O_L$ to be
the sum of the net flows out of all the vertices in $L$.  Since the net
flow out of each vertex in $L$ besides $S$ is zero, $O_L$ is
actually equal to the net flow out of $S$.

On the other hand, notice that in the sum which defines $O_L$, the flow
rate of each edge between vertices in $L$ appears positively and
negatively.  On the other hand, the flow rates on edges going between $L$
and $R$ are counted once---positively if the flow is directed from $L$ to
$R$, negatively otherwise.  These edges are exactly the edges in the cut
set that separates $L$ from $R$.  So $O_L$ is also equal to the sum of the
flows on edges in the cut set, positively if the edge flow is directed out
of $L$, negatively otherwise.  But the flow on each edge in the cut set
must be bounded by the capacity of the edge, so the magnitude of $O_L$ can
at most equal the sum of the capacities of the edges in the cut set.
Since the net flow out of $S$ equals $O_L$, it's magnitude is also bounded
by the capacity of the cut set.

  \end{solution}%
  }

\eparts

% miniquiz item...

\item Determine whether the following two graphs are isomorphic and
  show your reasoning.

\medskip

\centerline{\psfig{figure=figures/mq4p2.eps,height=2.5in}}

\omitsolution{%
  \begin{solution}
    
  \end{solution}
  }

%%%%%%%%%% PROBLEM %%%%%%%%%

\newpage %
\problem %
An {\em edge coloring} of a graph is an assignment of a color to each
edge of a graph so that no two edges that share an endpoint have the
same color.

\begin{problemparts}

\ppart Prove that a graph with maximum degree $\Delta$ MUST be colored
with at least $\Delta$ colors.

This is pretty tight, because a famous theorem of Vizing says that
every graph can be edge-colored with $\Delta$ or $\Delta+1$ colors.
We'll prove a special case.

\ppart Prove by induction that a graph with maximum degree $\Delta$
can be colored with at most $2\Delta-1$ colors.

\ppart Suppose every vertex in a graph has even degree.  Prove that
the graph's edges can be colored with two colors such that exactly
half the edges incident on each vertex have each color.  {\bf Hint:}
  consider alternating colors on an Euler tour of the edges.

\ppart Prove that a graph in which every edge has degree $2^k$ can be
edge-colored with exactly $2^k$ colors.

\ppart Prove that a graph with maximum degree $2^k$ can be colored
with exactly $2^k$ colors.
\end{problemparts}


\omitsolution{%
  \begin{solution}
    
  \end{solution}
  }

