\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}\induction


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

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

\problem {\bf (10 points)} 
Let $G_n$ be a directed graph with vertices numbered $0, 1,
\ldots, n-1$.  There is a directed edge from vertex $i$ to vertex $j$
if and only if $j \equiv i^2 + i + 1 \pmod{n}$.  (See page 119 of
Rosen for a definition of $\equiv$ and $\pmod{n}$.  As a hint,
however, no number theory is required to solve this problem.)

\begin{problemparts}

\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.

\begin{figure}[h!]
\centerline{\resizebox{4.0in}{!}{\includegraphics{figs/f98ps3-digraph.eps}}}
\end{figure}

\problempart Prove that if $n \geq 1$, then $G_n$ is not a directed
acyclic graph.

\solution{
\begin{proof}
Consider the following sequence of vertices in graph $G_n$.

\begin{eqnarray*}
v_1 & = & 0 \\
v_2 & = & v_1^2 + v_1 + 1 \pmod{n} \\
v_3 & = & v_2^2 + v_2 + 1 \pmod{n} \\
\ldots & & \ldots \\
v_{n+1} & = & v_n^2 + v_n + 1 \pmod{n}
\end{eqnarray*}

Note that there is a directed edge from $v_i$ to $v_{i+1}$ for all $1
\leq i \leq n$.  Not all of the vertices $v_1, \ldots, v_{n+1}$ can
be distinct, since the graph contains only $n$ vertices.  Suppose
$v_j$ is the first vertex in the sequence to appear a second time, and
$v_k$ was the initial appearance of that vertex.  Than the sequence of
vertices $v_k, v_{k+1}, \ldots, v_{j-1}$ forms a directed cycle.
Therefore, $G_n$ is not a directed acyclic graph.
\end{proof}
}

\end{problemparts}


\problem {\bf (20 points)} 
A {\em linear extension} of a poset is a
total order consistent with the partial order.  That is, if $x > y$ in
the partial order, then $x > y$ in the total order also.  For example,
in the poset defined by the Hasse diagram below, the following
relationships hold: $a > b$, $a > c$, $a > d$, $a > e$, $b > c$, and
$b > d$.

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-partial.eps}}}
\end{figure}

This poset has eight linear extensions, which are listed in the table below.  To
clarify the notation, the upper-left entry represents the total order
where $a$ is the largest element, $b$ the second largest, and so
forth.  Note that all of the relationships that hold in the poset also
hold for all the total orders listed below.

\[
\begin{array}{ccc}
a > b > c > d > e	& \quad \quad &		a > b > d > c > e \\
a > b > c > e > d	&	&		a > b > d > e > c \\
a > b > e > c > d	&	&		a > b > e > d > c \\
a > e > b > c > d	&	&		a > e > b > d > c
\end{array}
\]

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

\problem {\bf (15 points)} 
An {\em automorphism} of a graph is a relabeling of the
vertices that preserves adjacency.  For example, the graph on the left
side of the figure below has the automorphism $a \rightarrow b, b
\rightarrow a, c \rightarrow c, d \rightarrow d$.  (Here the
notation $x \rightarrow y$ means that the vertex labeled $x$ is
relabeled $y$.)  The relabeled graph is shown on the right side of the
figure.  This relabeling is an automorphism because adjacency is
preserved; that is, in the relabeled graph, just as in the original,
$a$ is adjacent to $b$ and $c$; $b$ is adjacent to $a$ and $c$; $c$ is
adjacent to $a$, $b$, and $d$; and $d$ is adjacent to $c$.  Every
graph has a {\em trivial automorphism} that assigns each node its
original label.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-auto.eps}}}
\end{figure}

\begin{problemparts}

\problempart List all non-trivial automorphisms of the graph below using the
$x \rightarrow y$ notation as in the example.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-findauto.eps}}}
\end{figure}

\solution{
\[
\begin{array}{c}
a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow g, h \rightarrow h \\

a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow h, h \rightarrow g \\

a \rightarrow a, b \rightarrow b, c \rightarrow c, d \rightarrow d,
e \rightarrow e, f \rightarrow f, g \rightarrow h, h \rightarrow g
\end{array}
\]
}

\problempart Draw a graph with at least 2 nodes that has only the trivial
automorphism.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figs/f98ps3-noauto.eps}}}
\end{figure}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
An $n$-node graph is said to be {\em tangled} if there is an edge
leaving every set of $\lceil\frac{n}{3}\rceil$ or fewer vertices.  As
a special case, the graph consisting of a single node is considered
tangled.  (Recall that the notation $\lceil x \rceil$ refers to the
smallest integer greater than or equal to $x$.)

\begin{problemparts}

\problempart Find the error in the proof of the following claim.

\bigskip

{\bf Claim.} Every non-empty, tangled graph is connected.

\bigskip

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
tangled, then it is connected.  In the base case, $P(1)$ is true
because the graph consisting of a single node is defined to be tangled
and is trivially connected.

In the inductive step, for $n \geq 1$ assume $P(1), \ldots, P(n)$ to
prove $P(n+1)$.  That is, we want to prove that if an $(n+1)$-node
graph is tangled, then it is connected.  Let $G$ be a tangled,
$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
the first piece contains exactly $\lceil\frac{n}{3}\rceil$ vertices,
and the second piece contains all remaining vertices.  Note that since
$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
contain at least one vertex.  By induction, each of these two pieces
is connected.  Since the graph $G$ is tangled, there is an edge
leaving the first piece, joining it to the second piece.  Therefore,
the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by strong induction.
\end{proof}

\solution{
The error is in the statement, ``By induction, each of these two
pieces is connected.''  This is not what the induction hypothesis
says; the induction hypothesis states that {\em if a graph is
tangled}, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form
``if (this), then (that)''.  However, we erroneously use the induction
hypothesis as if it were simply of the form ``(that)'.
}

\problempart Draw a tangled graph that is not connected.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1in}{\includegraphics{figs/f98ps3-tangled-cx.eps}}}
\end{figure}
}

\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
leaving every set of $\lceil\frac{n}{2}\rceil$ or fewer vertices.
Again, as a special case, the graph consisting of a single node is
considered mangled.  Prove the following claim.

\bigskip

{\bf Claim.} Every non-empty, mangled graph is connected.

\solution{
\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that these exists an $n$-node graph that is mangled, but
not connected.  Then the graph must have at least two connected
components.  However, there can be at most one connected component
with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
only $n$ vertices in total.  Therefore, there exists a connected
component with $\lceil\frac{n}{2}\rceil$ or fewer vertices.  Since the
graph is mangled, there is an edge leaving this component.  But this
contradicts the definition of a connected component.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  
Your diagram must be tidy to receive full credit.  In particular,
label all the vertices, e.g. $(b, 3)$, and use two different colors or
line styles (e.g. dashed and solid) to distinguish the two types of
edge defined above.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{figs/f98ps3-twographs.eps}}}
\end{figure}

\solution{
\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-product.eps}}}
\end{figure}
}

\problempart Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}

\end{problemparts}

%**************
%   PSET 4    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)}
Suppose that the dating game is played as described in class.  That
is, girls pursue their favorite boys, boys reject all but their top
prospect, and the game ends when each boy has a single candidate
remaining.  Prove or disprove each of the following assertions.

\begin{problemparts}

\problempart There is always some girl who gets her favorite boy.

\solution{The claim is false.  Suppose that there are three girls
named $A$, $B$, and $C$, and there are three boys named 1, 2, and 3.
Assume that the boys and girls have the preferences shown in the table
below.

\[
\begin{array}{l|l}
\text{girls' picks} & \text{boys' picks} \\ \hline
A : 1, 2, 3	&	1 : C, A, B \\
B : 2, 3, 1	&	2 : A, B, C \\
C : 2, 1, 3	&	3 : A, B, C
\end{array}
\]

The next table shows what happens during the dating game.  There is
one row for each boy, and a column for each stage of the game.  Each
entry lists all the girls pursuing a boy at a given stage.  The girl
rejected at each stage is crossed off.

\[
\begin{array}{c|l|l|l|l}
\text{boy}
& \text{stage 1}& \text{stage 2}& \text{stage 3}
& \text{stage 4} \\ \hline
1 & A		& \not\!\!A, C	& C		& C \\
2 & B, \not\!C	& B   		& A, \not\!\!B	& A \\
3 & 		&		&		& B
\end{array}
\]

In this case, every girl gets her second-favorite boy.
}

\problempart For every number of girls and boys, it is possible for
every boy to get stuck with his least favorite girl.

\solution{The claim is true.  If every girl has a different favorite
boy, then the algorithm terminates immediately and the boys'
preferences are irrelevant.  In particular, every boy may be stuck
with his least-favorite girl.}

\end{problemparts}

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

\problem {\bf (5 points)}
There are two girls, Alice and Betty, and two boys, Steve and Tim.
Alice prefers Steve, but the others' preferences are such that every
boy-girl dating arrangement is stable.  What are Betty, Steve, and
Tim's preferences?

\solution{
Steve prefers Betty, Betty prefers Tim, and Tim prefers Alice.

The key fact is that every dating arrangement must be stable.  If
Steve preferred Alice, then they would be a rogue couple if they were
not dating.  Therefore, Steve prefers Betty.  If Betty preferred
Steve, then they would be a rogue couple if they were not dating.
Therefore, Betty prefers Tim.  If Tim preferred Betty, then they would
be a rogue couple if they were not dating.  Therefore, Tim prefers
Alice.}

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

\problem {\bf (10 points)} Prove or disprove the following claim: for
some $n \geq 3$, there exists a set of boys' and girls' preferences
such that every dating arrangement is stable.

\solution{
The claim is false.

\begin{proof} We will use letters to denote girls and numbers to denoted boys.

There must be some girl $A$ rated worst by at most $n-2$ boys.  The
reason is as follows.  Each boy can rate exactly one girl worst.  If
each of the $n$ girls was rated worst by at least $n-1$ boys, then
there would have to be at least $n (n-1)$ boys in all.  But this is
false when $n \geq 3$, because then $n (n-1)$ exceeds $n$, the actual
number of boys.

Suppose that this girl $A$ is paired with the boy, 1, that she rates
worst.  Since at most $n-2$ boys rate girl $A$ worst, there is some
other boy, 2, that rates a different girl, $B$, worst.  Suppose that
boy 2 is paired with girl $B$.

Now girl $A$ and boy $2$ form a rogue couple.  Girl $A$ prefers every
other boy to her date, 1.  Similarly, boy $2$ prefers every other girl
to his date $B$.  Therefore, $A$ and $2$ prefer one another to their
current dates.
\end{proof}
}

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

\problem {\bf (15 points)} There are $n$ girls in a tennis tournament.
The tournament director hates to see anyone unhappy.  Therefore, he
plans to adjust the outcome of the tournament according to the
following rule: if a player loses all her matches, then he will change
all her losses to wins.  Of course, changing the results in this way
might create a new player who lost all her matches.  Therefore, his
plan is to continue applying his rule until there is no player who
lost all her matches.

The tournament is played and the results are reported to the director.
It so happens that the original tournament contains no cycles.  The
director now begins to adjust the results according to his rule.

\begin{problemparts}

\problempart Use a state machine model and the Invariant Theorem to
prove that the tournament director never creates a cycle through
repeated application of his rule.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  Define a state machine as
follows.  Let the set of states $Q$ be the set of tournaments.  Let
the set of start states $Q_0$ be an arbitrary acyclic tournament.  Let
the transition relation $\delta$ consist of tournament pairs $(T, T')$
where $T'$ is obtained from $T$ by applying the tournament director's
rule one time.

We will prove that the following invariant holds: the tournament is
acyclic.  In the start state, this invariant holds trivially.  For
each transition $T \rightarrow T'$ in $\delta$, assume that the
invariant holds for $T$ to prove that the invariant holds for $T'$.

Suppose that $p$ is the player with all losses in tournament $T$ that
has all wins in tournament $T'$.  There can be no cycle in $T'$ that
does not involve player $p$, since this would imply a cycle in $T$ as
well.  However, there can be no cycle in $T'$ that does involve
player $p$, since she wins all her matches in $T'$.

Thus the invariant is established by the Invariant Theorem.
\end{proof}
}

\problempart Prove that by applying his rule, the director can never
make everyone happy.  That is, no matter how many times he applies his
rule, there is still a player that lost all her matches.

\solution{
\begin{proof}
The preceding proof implies that the director never creates a
tournament with a cycle.  We will prove that if a tournament does not
contain a cycle, then there is player who lost all her matches.
Together these facts imply that the director can never create a
tournament where every player wins at least one match.

What remains is to prove that if a tournament does not contain a
cycle, then there is a player who lost all her matches.  We will
actually prove the contrapositive: if every player won at least one
match, then the tournament contains a cycle.

Form a sequence of players $p_1, p_2, \ldots, p_{n+1}$ as follows.
Let $p_1$ be an arbitrary player.  Let $p_2$ be one of the players
beaten by $p_1$, let $p_3$ be one of the players beaten by $p_2$, and
so forth.  We can form this sequence because every player won at least
one a match by hypothesis.  Since there are only $n$ players, some
player must appear more than once in the sequence $p_1, p_2, \ldots,
p_{n+1}$.  Let $p_j$ be the first player to appear a second time in the
sequence, and let $p_i$ be the first appearance of that player.  Then
the players $p_i, p_{i+1}, \ldots, p_{j-1}$ form a cycle.
\end{proof}
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Kavita's problems

%BEGIN Joe's problems %source: spring00 ps3
\problem A pair of 6.042 students, Nancy and David,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of David's copy of the notes for tutorial 2.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
  paraphernalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Nancy's cat, Muffy - 11 days, after task \#1.
\item {\bf Open a Starbucks chain} for the army to get their caffeine - 10 
days, after task \#3
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3, \#4, and \#5.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#6.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#6.
\end{enumerate}

Nancy and David want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.

\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Nancy cannot work on building a fleet for a few days, run get shots
for Muffy, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

%\begin{problemparts}
\problempart Express the information in the task list using some type
of graph (label the vertices to reflect task lengths).

\omitsolution{%
  \solution{%
    The information in the table is represented in the
    Figure~\ref{fig:tasks} in the form of a directed acyclic graph.
    Each vertex represents a task, and the weight of a vertex is the
    completion time.  Each directed edge represents a dependency
    between tasks.

    \begin{figure}[htbp]
      \centerline{\resizebox{!}{3.0in}{\includegraphics{figures/ps3-p9.eps}}}
      \caption{Graph representing the task precedence constraints.}
      \label{fig:tasks}
    \end{figure}
    }
  }

\problempart Give some valid order in which the tasks might be completed.

\problempart Nancy and David want to know how long conquering the
galaxy will take.  David suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\omitsolution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 11 + 10 + 4 + 6 + 8}{2} & = & 37 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Nancy and David from both working all the time.}

\problempart Nancy proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the longest sequence of tasks such that each
depends on the one before.  What lower bound does this give, and why
might it also be too low?

\omitsolution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), opening a Starbucks (10 days), training the 
army (4 days), and then
defeating Microsoft (8 days).  Since these tasks must be done
sequentially, galactic conquest will require at least 39 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Nancy and David may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Nancy and David
need to conquer the galaxy?  No proof is required.

\omitsolution{
40 days.  Tasks could be divided as follows:
\newline
David: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days 33-40).
\newline
Nancy: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days 33-38).
\newline

}

%\end{problemparts}

\problem %source: spring00 ps4
A 2-colorable graph is called {\em bipartite} (two pieces).

\begin{problemparts}
  \ppart Prove by induction that every tree is bipartite.
  \omitsolution{
\begin{solution} We first prove the following claim:

\begin{lemma*}
By a {\em leaf} in a graph, we mean a vertex of degree $1$.
We prove that every tree on at least $2$ nodes has a leaf.
\end{lemma*}
\begin{proof}
Let $T$ be a tree, and let $P$ be a simple path in $T$ of maximum
length.  (Because we disallow repeated vertices, the length of any
simple path is upper-bounded by the number of vertices in $T$.  This
implies there must be at least one simple path with maximum length.)

Suppose that $P = \{v_1, v_2 \ldots, v_k\}$ in this order.  We claim
that $v_1$ is a leaf.  For if not, then there is an edge $(v,v_1)$ in
$T$, where $v \neq v_2$.  Now if $v \not\in P$, we can attach $v$ to
the end of $P$ to obtain a longer path --- a contradiction.  But if $v
\in P$, then since $v \neq v_2$, this will give a cycle in $T$ ---
also a contradiction.
\end{proof}
Given this fact, we prove the theorem by induction on $n$.
\begin{proof}
Base case: $n = 1$.  We can color the single node anything we want,
thereby using at most two colors.

Inductive step.  Suppose that we know that every tree on $n$ nodes
is bipartite, for some $n \geq 1$.  Let $T$ be a tree on $n+1$ nodes;
we need to show how to two-color it.  Since $n+1 \geq 2$, we know
that $T$ has a leaf $v$.  Let $w$ be the unique neighbor of $v$.
Let $T' = T - \{v\}$.  Note that $T'$
is a tree, since it is still connected and has no cycles.
Thus, by the induction hypothesis, we can two-color it.  

Now we define the following two-coloring of $T$.  If $u$ is a vertex
of $T$ not equal to $v$, give $u$ the color that it had in our 
two-coloring of $T'$.  Then give $v$ whichever color we didn't give
to its neighbor $w$.  As this is a valid two-coloring of $T$, this
completes the inductive step and the proof.
\end{proof}
\end{solution}
}


  \ppart Prove that a graph is bipartite if and only if every simple
  cycle is of even length. ({\bf Hint:} Can $v$ have both an even and
  an odd length path to $w$?)

\omitsolution{
\begin{solution}
Assume a graph has a simple cycle of odd length.  Let the cycle be
$v_1,v_2,\ldots, v_n,v_1$, where $n$ is odd. Suppose that two colors
(red and blue) sufficed to color the graph containing this circuit.
Without loss of generality let the color of $v_1$ be red. Then $v_2$
must be blue, $v_3$ must be red, and so on, until finally $v_n$ must
be red (since $n$ is odd). But this is a contradiction, since $v_n$ is
adjacent to $v_1$.  Therefore at least three colors are needed. Hence
a graph is 2-colorable only if every simple cycle is of even
length. 

Conversely, assume the graph has no simple cycle of odd length. We
show that it is possible to color the graph using two colors. Without
loss of generality, assume that the graph is connected. (As otherwise
we can repeat the argument for each connected component of the
graph). Select a node, say $m$, in the graph and color it red. Color
all the nodes adjacent to $m$ blue. Call the set of all such nodes
$S_1$.  Now color all the nodes that are adjacent to the nodes in
$S_1$ but have not yet been colored, red.  Call the set of all such
nodes $S_2$.  Continue this process until you have colored all the
nodes. We now show that no two nodes in $S_i$ are connected by an
edge, for all $i$.  This is sufficient to establish that our coloring
is valid, since two adjacent nodes are either in the same set $S_i$
--- which we are going to show can't happen --- or are in two
consecutive sets $S_i$ and $S_{i+1}$ that are colored differently.
This is true because if one vertex gets included in $S_i$ before its
neighbor is colored, then the neighbor will be colored in the next
step.

Assume that we can find two nodes $u$ and $w$ in some
set $S_i$ that are adjacent in the graph. If $u$ and $w$ are adjacent
to a node in $S_{i-1}$ then we have a simple cycle of length $3$,
which is impossible.  So let $u_{i-1}\neq w_{i-1} \in S_{i-1}$ be
nodes adjacent to $u$ and $w$ respectively.  Now if $u_{i-1}$ and
$w_{i-1}$ are adjacent to a single node in $S_{i-2}$, say $c$, then
$u,u_{i-1},c,w_{i-1},w,u$ is a simple cycle of length 5, which is
impossible.  So let $u_{i-2}\neq w_{i-2}\in S_{i-2}$ be nodes adjacent
to $u_{i-1}$, and $w_{i-1}$ respectively. Continuing this way we
arrive at nodes $u_1\neq w_1 \in S_1$. However these are adjacent to
$m$.  This gives us a simple cycle
$m,u_1,u_2,\ldots,u_{i-1},u,w,w_{i-1},w_{i-2}\dots,w_1,m$, where
$u_j,w_j\in S_j$. But this cyle has length $2i+1$, which is odd,
hence a contradiction. Therefore, for all $i$ we do not have two nodes
in $S_i$ that are connected by an edge.  Therefore our coloring is
valid.  
\end{solution}
}

\ppart Explain why (a) follows immediately from (b).
\omitsolution{
\begin{solution}
Since a tree has no simple cycles, it has no simple cycles of odd
length, and thus (a) follows directly from (b).
\end{solution}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problemparts}

\problem %source: spring00 ps4b
Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$ be a
function associating a real number with each vertex.  Suppose $r$
satisfies the property that for each $v\in V$ such that $v$ has at
least one neighbor, the value $r(v)$ is the average of the values of
$v$'s neighbors.  Prove that if the graph is connected, then
$r(u)=r(v)$ for all $u,v\in V$.

\omitsolution{
\begin{solution}
\emph{not done yet.}
\end{solution}
}

\problem %source: spring00 ps5
Attached to this problem set are some students' solutions
from a previous problem set.  Mark up these solutions, indicating
things that are incorrect or unclear, and if possible show how the
solution can be made completely correct and clear.  Please refer to
the 6.042 course webpage for more readable versions of the students'
solutions.

\omitnonsolution{

\clearpage
\problempart Problem Set 4, Problem 1
%in GraphsTreesToursPaths.tex, search for
%''if removing the edge disconnects the graph''

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/ps5student2.ps}}}

\clearpage%
\problempart Problem Set 4, Problem 2
%in GraphsTreesToursPaths.tex, search for
%''function associating a real number with each vertex''

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/ps5student1.ps}}}

}


%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%  S99 ps3


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

\problem {\bf (10 points)} The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
correponds to row and column $i$ of the matrix.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/adjgraph.eps}}}
\bigskip
}

\problempart Determine the chromatic number of this graph, and
give a coloring of the vertices that uses the minimum number of
colors.

\solution{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}

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

\problem {\bf (10 points)} Let $G$ be a graph.  Prove that there is a
path from every vertex of odd degree to some other vertex of odd
degree.

\solution{
\begin{proof}
If graph $G$ has no vertex of odd degree, then the claim is true
vacuously.  Otherwise, let $v$ be a vertex of odd degree.  Consider a
longest path starting at $v$ in which each edge occurs at most once.
Then every edge leaving the final vertex on the path must already be
on the path.  We will show that this final vertex of the path is
another vertex of odd degree.

Since $v$ has odd degree, the path contains at least one edge.
Furthermore, the final vertex of the path cannot be $v$, since the
edges incident to $v$ would then consist of the first and last edge of
the path plus two edges for each time that the path crosses $v$--- an
even total.  Therefore, the edges incident to the final vertex of the
path consist of the final edge of the path plus two edges for each
time that the path crosses the final vertex--- an odd total, as
claimed.
\end{proof}
}

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

\problem {\bf (15 points)} An edge of a connected graph is called a {\em
cut-edge} if removing the edge disconnects the graph.  Prove that an
edge $e$ in a connected graph $G$ is a cut-edge if and only if no
simple cycle contains $e$.

For this problem, use the definition of a ``simple cycle'' given on
page 468 of Rosen (p.463 in ed.3).  (The lecture notes require a
simple cycle to have no repeated vertex, but Rosen requires no
repeated edge.)

\solution{
\begin{proof}
First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.  (Which sequence is
substituted for edge $e$ depends on the direction in which the path
$P$ traverses the edge $e$.)  This shows that the graph remains
connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}
}

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

\problem {\bf (15 points)} A graph $G$ is {\em self-complementary} if
$G$ and $\bar{G}$ are isomorphic.  The symbol $\bar{G}$, where $G$ is
a graph, is defined in problem 33 on page 456 of Rosen (p.449 in
ed.3).  The term ``isomorphic'' is defined on page 460 of Rosen (p.454
in ed.3).

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solution{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/selfcomp.eps}}}
\bigskip
}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solution{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is congruent to either 0 or 1 mod 4.

\solution{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}


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

\problem {\bf (10 points)} Consider the following table of exchange
rates.  A table entry indicates that one unit of row-currency can be
exchanged for the given amount of column-currency.

\bigskip
\centerline{
\begin{tabular}{c|ccccc}
	    & \$ US & pounds & \$ Canada & euros & rubles \\ \hline
\$ US		& 1.00	& 0.61	& 1.49	& 0.89	& 24.50 \\
pounds		& 1.62	& 1.00	& 2.43	& 1.44	& 40.85 \\
\$ Canada 	& 0.66	& 0.42	& 1.00	& 0.59	& 16.50 \\
euros 		& 1.12	& 0.69	& 1.69	& 1.00	& 28.23 \\
rubles		& 0.04	& 0.02	& 0.05	& 0.03	& 1.00
\end{tabular}
}
\bigskip

%  I assume that the real values of the currencies in US dollars are as
%  follows:
%
%    $ US	pounds		$ Canada	euros		rubles
%    1.00	1.63		0.67		1.13		0.04
%
%  I want most transaction to be lose money, but I'll create a path
%  ($ US -> euros -> $ Canada -> pounds -> rubles -> $US) that
%  makes money.  There might be a shorter cycle that makes money
%  overall, though not with every trade.  Furthermore, I've ensured
%  that one can't do ($ US -> somthing -> $ US) and make money.

\begin{problemparts}
\problempart Express the information in this table using some type of
graph.

\solution{We can represent this table using a weighted, directed graph
as shown below.

\bigskip
\centerline{{\bf Picture to be added.}}
%\centerline{\resizebox{!}{2.5in}{\includegraphics{figs/exchange.eps}}}
\bigskip
}

\problempart Suppose that I have 100 US dollars, and I want to
increase my number of dollars through a sequence of currency
exchanges.  Identify the abstract property that your graph must
possess in order for this to be possible and determine whether or not
your graph has this property.

\solution{There must be a direct cycle containing the US vertex such
that the product of the weights around the cycle is greater than 1.
The graph does contain at least one such cycle, which is shown with a
dotted line above.  The product of the weights around this cycle is
$1.0322\ldots$.}

\end{problemparts}

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

\problem {\bf (15 points)} This problem concerns Hamiltonian circuits
in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
traversing every vertex in the graph exactly once.  The $n$-cube is
defined on page 448 of Rosen (p.441 in ed.3).  (Rosen also uses the
name $Q_n$ for an $n$-cube.)  However, the following recursive
definition of an $n$-cube is equivalent to the one given in Rosen, but
may simplify your solutions.  A 0-cube is a single vertex.  An
$(n+1)$-cube consists of two $n$-cubes with corresponding vertices
joined by edges.  For example, a cube is two squares with
corresponding corners joined.

\begin{problemparts}
\problempart Draw a 4-cube.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/fourcube.eps}}}
\bigskip
}

\problempart In your drawing, highlight a Hamiltonian circuit.

\solution{The dotted edges in the diagram above form a Hamiltonian
circuit.}

\problempart Use induction on $n$ to prove that an $n$-cube has a
Hamiltonian circuit for all $n \geq 2$.

\solution{The proof is by induction.  Let $P(n)$ be the proposition
that an $n$-cube has a Hamiltonian circuit.  In the base case, $P(2)$
is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an $n$-cube has a Hamiltonian
circuit to prove that an $(n+1)$-cube has a Hamiltonian circuit.
Regard an $(n+1)$-cube as two $n$-cubes with corresponding vertices
joined.  The first $n$-cube has a Hamiltonian circuit $H$ by
induction, and there is a matching Hamiltonian circuit $H'$ in the
second $n$-cube.

Take an edge $(u, v) \in H$ and the corresponding edge $(u', v') \in
H'$.  We can construct a Hamiltonian circuit in the $(n+1)$-cube by
starting at vertex $u$, traversing the circuit $H$ all through the first
$n$-cube until reaching vertex $v$, crossing the edge $(v, v')$,
traversing the circuit $H'$ all through the second $n$-cube until
reaching vertex $u'$, and then crossing the edge $(u', u)$.
}
\end{problemparts}

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


\problem {\bf (10 points)} The weighted graph below represents a system
of pipes.  The weight on an edge is the {\em 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 capacity of the system; that is, the
maximum rate at which water can pass through the entire system in
gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/flowprob.eps}}}
\bigskip

\begin{problemparts}

\problempart Redraw the system of pipes.  For each pipe, indicate a
rate and direction of flow through the pipe so that the rate of flow
through the entire system is as large as possible.  Make sure that the
rate of flow through a pipe does not violate the limit given in the
diagram above.  Also, make sure that rate of flow into each vertex is
equal to the rate of flow out of the vertex (excluding vertices $S$
and $T$).  This establishes a lower bound on the capacity of the
system.

\solution{With the flow rates and directions shown below, the rate of
flow through the entire system is 7 gallons per second.  Therefore,
the capacity of the system is at least 7 gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/flowsol.eps}}}
\bigskip
}

\problempart Find a set of pipes with minimum total capacity such that
removing those pipes from the system completely disconnects vertex $S$
from vertex $T$.  Mark these pipes on your diagram.  This establishes
an upper bound on the capacity of the system; the rate of flow from
$S$ to $T$ can be no greater than the total capacity of this set of
pipes.

\solution{The edges marked with X's in the diagram have a total
capacity of 7 gallons per second.  Removing these edges disconnects
$S$ from $T$.  Therefore, the capacity of the system is at most 7
gallons per second.}

\end{problemparts}

To receive full credit, your lower bound on the capacity of the system
from part (a) must equal your upper bound from part (b).


%%%%%%%%%%%% S99 ps4


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

\problem {\bf (15 points)} Unfortunately, I was not able to turn in my
problem set for 6.042 and I need to meet my TA to get it in.  We are
both driving through the city and in order for me to turn in the
problem set we must meet at exactly the same place at the same time.
Given the following map,

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/map1.eps}}}
\bigskip

\begin{problemparts}
\problempart At each time step, both I and my TA simultaneously move to an
adjacent node in the graph.  We would like to organize our routes such
that we meet at the same node at the same time.  Can we do it?

\solution

No.  I cannot meet my TA on this map: There is no even-length path
that connects the two nodes we are placed on.  Note that a solution
exists if and only if there is an even-length path between the nodes
that I and my TA initially occupy (a path could traverse the same
nodes and edges many times).  You can convince yourself that there is
no even-length path in this example by noting that every simple path
connecting the two nodes has odd length, and furthermore, that this
graph has only even-length cycles, and hence no amount of loops attached
to any of the simple paths can create an even-length path.

In part (c) we will argue that there is an even-length path between
every two nodes on the graph if the graph is connected and not
bi-partite.  The graph in this example is connected but it {\em is}
bi-partite, and if we 2-color it (i.e. partition its vertices into
two disjoint sets $V_1$ and $V_2$ s.t. there is no edges within $V_1$
and no edges within $V_2$) then me and my TA both occupy a node of the
same color.

\problempart How about if we used the following map instead?

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/map2.eps}}}
\bigskip

\solution

Yes.  Now there is an odd-length path between the two nodes.  Note
that this graph is connected but not bipartite.  Note also that, in
contrast to the previous graph, this one has an odd cycle.

\problempart Describe a general criterion for a graph where I would be able
             to meet my TA at some vertex regardless of our initial positions.

\solution

Such graph must have an even-length path between every two nodes.  A graph
with two or more vertices has this property if and only if it is
connected and not bipartite.  Here is a proof:

\noindent
($\Rightarrow$) Suppose there is an even length path between every two
vertices.  Since there is a path between every two vertices, the graph is
certainly connected.  Now supppose the graph was also bipartite.  On any
path in a bipartite graph, the successive vertices alternate colors. So if
the path has even length, the first and last colors will agree.  Since
every two vertices are connected by an even length path, every pair of
vertices has the same color.  In particular, the endpoints of any edge
must have the same color, a contradiction.  Hence the graph cannot be bipartite.

\noindent
($\Leftarrow$)
Suppose a connected graph has a pair of vertices $v \neq w$ such that
there is no path of even length between $v$ and $w$.  We will show that
the graph is bipartite.

Let $E$ be the set of vertices reachable by an even length path from $v$,
and let $O$ be the vertices reachable by an odd length path from $v$.  We
claim that coloring vertices in $E$ white and coloring vertices in $O$
black is a 2-coloring of the graph.

First of all we must show that this rule really defines a coloring.  Since
every vertex other than $v$ is reachable from $v$ by a path whose length
must be even or odd, every vertex besides $v$ gets assigned a color.  But
$v$ also gets a color: leaving and returning to $v$ using the same path in
both directions is an even length path from $v$ to $v$, so $v$ gets
colored white.

Moreover, every vertex will be assigned a unique color.  To verify this,
we must show that no vertex is in both $E$ and $O$.  But suppose $E$ and
$O$ had a vertex, $x$, in common.  This means there is an odd-length path,
$p_o$, and also an even length path $p_e$, each going from $v$ to $x$.
But because the graph is connected, there is also a path, $q$, from $x$ to
$w$.  Now the paths $p_oq$ and $p_eq$ both go from $v$ to $w$, and one of
them must be of even length, a contradiction.  So $E$ and $O$ are indeed
disjoint.

All that remains is to show is that there is no edge between distinct
vertices in $E$ nor between distinct vertices in $O$.  Suppose there was
an edge with endpoints $y \neq x$ which were both in $E$.  Then the even
length path from $v$ to $y$ followed by the edge $(y,x)$ is an odd length
path from $v$ to $x$, so $x$ is in $O$ as well as $E$, which we know is
impossible.  Similarly, there can't be an edge between two vertices in $O$.

So we have shown that the graph is bipartite. \qed

\iffalse

\bigskip\noindent{\bf Solution 2:}

Another solution to this problem was to argue that a graph has an
even-length path between every two nodes if and only if it is
connected and has an odd cycles.  This statement will follow from the
solution above and from the following theorem:
\begin{quote}
{\bf Theorem:} {\it
A graph is bipartite if and only if it has no odd cycles.}
\end{quote}
Here is the proof:

\noindent
($\Rightarrow$)

To say that a graph is bipartite is the same as to say that it is
2-colorable.  If $G=(V,E)$ is bipartite, then let $R,B$ (for red and
blue) $R\cap B=\emptyset, R\cup B=V$ be the two-coloring of $G$.  Take
any node $v_0$ in $V$, and any path $v_0,v_1,v_2,...,v_n,v_0$ that
goes from $v_0$ to $v_0$ (in other words, take any cycle in $G$).
Assume without loss of generality that $v_0\in{R}$.  Then it must be
that $v_i\in{R}$ if $i$ even and $v_i\in{G}$ if $i$ odd.  Hence $n$
must be odd and the length of the cycle is even.

\noindent
($\Leftarrow$)

We give a proof by induction on $n=|E|$, $n\geq{0}$.  The predicate we
will prove is the following: $P(n)=$``For every graph $G=(V,E)$ for
$|E|=n$, if $G$ has no odd cycles then $G$ is bipartite'':

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because a graph with no edges is both
bipartite and has no odd cycles.

\medskip
\noindent 
%
{\em Inductive case:} Take some $n\geq{1}$.  We will show that if
$P(n-1)$ then $P(n)$.  Take some $G=(V,E)$ s.t. $|E|=n$.  Assume $G$
has no odd cycles.  Pick an edge $e=(v,u)\in{E}$ and remove it to
create a graph $G'=(V,E')$ where $E'=E\setminus\{e\}$.  Then $|E'|<n$
and $G'$ has no odd cycles, since $G$ did not have any.  Hence, from
$P(n)$ it follows that $G'$ is bipartite.  Let $R,B$ be a
two-coloring of $G'$.  We have two cases: First, if $u\in{R}$ and
$v\in{B}$ or vice versa, then the same $(R,B)$ is a two-coloring for
both $G'=(V,E')$ and $G=(V,E)$ and hence, in this case, $G$ is
bipartite.  The other case is if $u,v\in{R}$ (or $u,v\in{B}$, but
without loss of generality we can assume the former).  We have two
cases here:
\begin{enumerate}
\item
If $u$ and $v$ are not connected in $G'$ then we can invert the colors
in the connected (in $G'$) component $C\subseteq{V}$ to which $v$
belongs (and keep the colors of the vertices that do not belong to the
connected component $C$).  In result we will get another good
two-coloring of $G'$, but now $u$ and $v$ have a different color.
Hence this case looks like the one we looked at above.
\item
If $u$ and $v$ are connected in $G'$, then since they have the same
color in a two-coloring of $G'$, there is an even-length path between
them in $G'$.  But then adding an edge $(u,v)$ to $G'$ creates an
odd-length cycle, which contradicts the assumption that $G$ has no
odd-length cycles.
\end{enumerate}
\fi


\end{problemparts}

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

\problem {\bf (15 points)} A rooted tree is called \emph{finite-path} iff
it has no infinite simple paths starting at the root.

A finite-path tree need not be finite nor even have an upper bound on the
length of its paths.  For example, there is a finite-path tree whose root
has an infinite number of children and each child of the root is at the
top of a finite chain of descendents one longer than the previous child's.
The first seven branches of this tree are shown in
Figure~\ref{fin-path-tree}.

\begin{figure}[htbp]
\centerline{\psfig{figure=figs/fptree.eps,height=3in}}
\caption{\em The first seven branches of a finite-path tree with paths of
every finite length.}
\label{fin-path-tree}
\end{figure}

Let $\preceq$ be the binary relation on rooted trees ``is (isomorphic to)
a proper subtree of.''  That is, $T_1 \preceq T_2$ iff there is a
\emph{non-root} vertex $v$ of $T_2$ such that $T_1$ is isomorphic to the
subtree of $T_2$ rooted at $v$.

\begin{problemparts}

\problempart Prove that $\preceq$ is a well-founded partial order on
finite-path trees.  (Use the definition of a partial order from Tutorial 3
which does not require that a partial order be reflexive).

\solution

We need to show that $\preceq$ is transitive and anti-symmetric:

\begin{itemize}
\item
$\preceq$ is transitive: Suppose a copy of $T_1$ is a subtree of $T_2$;
then there is path, $P$, from the root of the $T_1$-copy to the root of
$T_2$.  Suppose also that a copy of $T_2$ is a subtree of $T_3$; then
there is path, $Q$, from the root of the $T_2$-copy to the root of $T_3$.
Now the $T_2$-copy has a copy of the $T_1$-copy as a subtree; call this
subtree $T'_1$.  So the path $P$ has a copy, $P'$, from the root of $T'_1$
to the root of the $T_2$-copy.  This means that the path $P'$ followed by
the path $Q$ leads from the root of $T'_1$ to the root of $T_3$.  So
indeed, there is a copy of $T_1$, namely $T'_1$, which is a proper subtree
of $T_3$.

\item
We show that $\preceq$ is anti-symmetric: Suppose (a copy of) $T_1$ is a
proper subtree of $T_2$ and also $T_2$ is a proper subtree of $T_1$.  Then
$T_1$ has a copy of itself as a proper subsubtree.  Therefore there is a
path --- which must be of length two or more --- from the root of $T_1$ to
the root of the copy of $T_1$.  This path extends to a path of length four
or more to the root of the copy in the copy, and then extends to the root
of the copy in the copy in the copy\dots.  In this way we can find an
infinite path in $T_1$, contradicting the assumption that $T_1$ is
finite-path.
\end{itemize}

Now we must show that $\preceq$ is well-founded.  Suppose not.  Then, as
shown in Handout 18 on well-founded posets, there must be an infinite
$\preceq$-decreasing sequence of distinct elements.  That is, an infinite
sequence $T_1 \succ T_2 \succ T_3 \succ \dots$ of distinct finite-path
trees.  By definition, $T_n \succ T_{n+1}$ means there is a path from the
root of $T_n$ to a vertex which is the root of an isomorphic copy of
$T_{n+1}$.  It's convenient to assume that $T_{n+1}$ itself --- rather
than an isomorphic copy --- is the subtree of $T_n$.  This assumption
is justified because we could always replace $T_{n+1}$ in the sequence
above with the actual subtree of $T_n$ isomorphic to it.

Now $T_n \succ T_{n+1}$ implies there is a path $P_n$ (necessarily of
length one or more) from the root of $T_n$ to the root of $T_{n+1}$.  But
then $P_1$ followed by $P_2$ followed by $P_3$ \dots is an infinite path
from the root of $T_1$, contradicting the hypothesis that $T_1$ is
finite-path.  Hence there cannot be such an infinite decreasing sequence
of finite-path trees, and this implies that the set of finite-path trees
partially ordered by $\preceq$ is a well-founded poset.  \qed


\problempart In Problem 7 of Problem Set 3, we established that for
any two-person game with a \emph{finite} game tree, at least one
player has a non-losing strategy.  Show that this result in fact holds
for all two-person games with a \emph{finite-path} game tree.

\solution

Problem 7(b) of Problem Set 3 established a stronger fact about game
trees: either one player has a winning strategy or both players have
nonlosing strategies.  In the solutions for Problem Set 3, the first
solution of 7(b) used induction on tree depth and so only applied to trees
of finite depth.  However, the second solution given for 7(b) only used
the fact that the ``proper subtree'' relation is a well-founded partial
order, and so it applies \emph{without change} to finite path trees.

\problempart Here is an example of a game.  Player one chooses a triple of
natural numbers.  Then players alternate choosing triples of natural
numbers.  Any triple may be selected as long as it is \emph{not}
coordinate-wise $\geq$ any previously selected triple.  The game ends
when a player picks the triple $(0,0,0)$; this player loses.

For example, player 1 might first choose (7,8,9).  Player 2 could then
choose (0,1,67), and after that Player 1 could choose (83, 0,0).  Player 2
can then choose (1,0,0).  Now player 1 can choose (0,0,1), allowing player
2 to choose (0,1,0).  This finally leaves player 1 with only the losing move
(0,0,0).

\iffalse In other words, if the first $n$ moves in the game are
$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ where $(x_i,y_i)$ pairs with odd $i$'s
were picked by player A and those with even $i$'s were picked by player B,
then the next player (A if $n+1$ is odd or B if $n+1$ is even) can pick a
pair of natural numbers $(x_{n+1},y_{n+1})$ only if there is no $k$,
$1\leq{k}\leq{n}$ s.t. $x_{n+1}\geq{}x_k$ {\em and} $y_{n+1}\geq{}y_k$.\fi

Show that one of the players must have a winning strategy.  \hint Use the
results about well-quasi-orders from Tutorial 4.

\solution

In Problem 2 of Tutorial 4, we studied a more general version of the
game above, where the first player chose $n$, which sets up a
``dimension of the board they play on''.  The game above, is like the
game from Tutorial 4 where the first player always picks $n=3$, and so
all consequent moves are {\em triples} of natural numbers.  We can use
similar logic as in that problem to argue the following:
\begin{enumerate}
\item
Let's first cast the question of whether moves in this game are valid
or not in terms of some partial ordering in set $\naturals^3$:

A sequence $p_1,p_2,p_3,...,p_n$ (or an infinite sequence
$p_1,p_2,p_3,...$) of points in $\naturals^3$ (i.e. a sequence of
triples of natural numbers) is a {\em valid sequence of moves} in this
game (alternating moves of player A and player B), if and only if
\[
\forall(i,j)\,\, i<j \Rightarrow p_i \not\leq_3 p_j
\]
where relation $\leq_p$ is a partial order in $\naturals^3$ defined
as follows:
\[
(x_1,y_1,z_1) \leq_3 (x_2,y_2,z_2) ~~~\iff~~~
((x_1\leq{x_2})\wedge(y_1\leq{y_2})\wedge(z_1\leq{z_2}))
\]

\item
First note that $(\naturals,\leq)$ is a well-quasi-ordered set. Here is
a definition from Tutorial 4:
\begin{quote}
{\bf Definition 4.1:} {\it
A poset $(P,\preceq)$ is \emph{well-quasi-ordered} iff, for every infinite
sequence $p_1, p_2, \dots p_n \dots$ of elements in $P$, there are positive
integers $i<j$ such that $p_i \preceq p_j$.}
\end{quote}
The well-quasi-ordered property of $(\naturals,\leq)$ is immediate: any
infinite sequence of distinct natural numbers $n_1,n_2,n_3,...$ must
eventually include a number larger than $n_1$, and so must be a sequence
of the required kind.

\item
Now we can use the findings of Problem 2 in Tutorial 4 to argue that
set $(\naturals^3,\leq_3)$ is well-quasi-ordered.  We use Lemma 4.2 of
part (e) of Problem~2:
\begin{quote}
{\bf Lemma 4.2:} {\it
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \times Q$ under the coordinate-wise partial order.}
\end{quote}
This lemma implies that since $(\naturals,\leq)$ is a
well-quasi-ordered poset by point (2) above, then so is $(\naturals^2,
\leq_2)$ where $\leq_2$ is a coordinate-wise partial order in
$\naturals^2$.  And applying the lemma once more, we get that
$(\naturals^3, \leq_3)$ is a well-quasi-ordered poset too.

\item
As in Part (e) of Problem 2, by bringing together point (1) and (3)
above, we realize that since $(\naturals^3,\leq_3)$ is
well-quasi-ordered, then in every infinite sequence of points
$p_1,p_2,p_3,...$ in $\naturals^3$, there must be a pair $(i,j)$,
$i<j$ s.t. $p_i\leq{p_j}$.  By point (1), this means that no infinite
sequence of points in $\naturals^3$ can be a sequence of valid moves
in this game.  Hence, every sequence of valid moves in this game is
finite (In particular, the game can never go on for ever).

\item
The fact that there can be no infinite sequence of valid moves in this
game means this game has a {\em finite-path} game tree.  Therefore,
the result from part (b) of this problem above applies here, i.e. one
of the players has a non-losing strategy.  But since there is no
``draw'' outcome in this game, a non-losing strategy must be a
winning strategy.

\end{enumerate}

\problempart \emph{Extra Credit}: Who has a winning strategy?  What is
the strategy?   \textbf{(We don't known the answer.)}

\iffalse
\stas{See what the students write and tell me if there are some
different strategies.  For $n=2$, there is a winning strategy for
player A: It should pick $(1,1)$ and then respond to every $(x,y)$
with $(y,x)$, unless $(x,y)=(0,0)$ and player B looses.  But I dont
see how to translate it into a 3-D strategy easily...  Please email
everyone if you see a light.}
\fi
\end{problemparts}





%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset3 problem1 spring98 (Rosen 7.3-32)
\problem [10 pts]

The graphs  $C_n$, $Q_n$, $W_n$, and $K_{n,m}$ are defined in Rosen 7.2.

\bparts

\ppart Describe the adjacency matrix for $C_n$.

\solution{
For $C_n$, we label the vertices so that the cycle goes 
$v_1,v_2,\ldots,v_n,v_1$.  Then the matrix has 1's on the diagonals just 
above and below the main diagonal and in positions $(1,n)$ and $(n,1)$,
and 0's everywhere else. 

\begin{gather*}
\begin{pmatrix}
0 & 1 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 1 & 0 &\ldots & 0 & 0\\
0 & 1 & 0 & 1 &\ldots & 0 & 0\\
0 & 0 & 1 & 0 &\ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 &\ldots & 0 & 1\\
1 & 0 & 0 & 0 &\ldots & 1 & 0\\
\end{pmatrix}
\end{gather*}
}

\ppart Describe the adjacency matrix for $K_{n,m}$.

\solution{
Vertices of $K_{n,m}$ are partitioned into a group of $n$
vertices and a group of $m$ vertices. In this graph, an edge is
present between two vertices if and only if the two vertices are from 
different groups.
Therefore, the adjacency matrix of $K_{n,m}$ consists of
four sub-matrices. The top left and the bottom right matrices
consist of 0's with size $n * n$ and $m * m$ respectively.
The top right and the bottom left matrices consist of 1's
with size of $n * m$ and $m * n$ respectively.
 
 
\begin{gather*}
\begin{pmatrix}
0 & \ldots & 0 & 1 & \ldots & 1\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \ldots & 0 & 1 & \ldots & 1\\
1 & \ldots & 1 & 0 & \ldots & 0\\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \ldots & 1 & 0 & \ldots & 0\\
\end{pmatrix}
\end{gather*}
}

\ppart Give a simple recursive definition of the adjacency matrix for the
graph $Q_{n+1}$.  \hint Use the matrix of $Q_n$ and suitable identity
matrices.

\solution{
The base case is,
 
\begin{gather*}
Q_1 =  
\begin{pmatrix}
0 & 1\\
1 & 0\\
\end{pmatrix}
\end{gather*}
 
Then, every $Q_{n+1}$ ($n \geq 1$) is defined inductively. 
The size of $Q_{n+1}$ is
$2^{n+1} * 2^{n+1}$ and the left top and right bottom quarter of the matrix
are $Q_n$, which correspond to the two subgraphs $Q_n$ in $Q_{n+1}$. The right top and left bottom quarter of the matrix
are identity matrices of size $2^n*2^n$($I_{2^n}$), which correspond to the 
edges connecting vertices $k$ and $k+2^n$ for $0\leq k<2^n$, which differ by the most 
significant bit only.

\begin{gather*}
Q_{n+1} =
\begin{pmatrix}
Q_n & I_{2^n} \\
I_{2^n} & Q_n \\
\end{pmatrix}
\end{gather*}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset3 problem2 spring98
\problem [10 pts]

Find the minimum number of colors to color (with no two adjacent
vertices given the same color, {\em cf.} Rosen, 7.8) each of $C_9, C_{20},
W_{13}$ and $K_{311,222}$.  Explain briefly.

\solution{
$C_9$ and $C_{20}$ can be colored with $3$ and $2$ colors respectively.
To see this, let's number the vertices of $C_n$ from $1$ to $n$ 
by going around the cycle. If $n$ is even,
we can assign every even vertex with one color and every odd vertex
with the other color. Since  $n$ is even and $1$ is odd, vertex $n$ and vertex 1
 will have 
different colors. Therefore, we only need $2$ colors.


If $n$ is odd, we need one more color, since both $1$ and $n$ are odd and
they cannot have the same color. Therefore, we will assign
all the even vertices with one color, all the odd vertices except $n$ with
a second color and $n$ with a third color. Therefore, we need $3$
colors. Since 9 is odd and 20 is even, $C_9$ and $C_{20}$ need $3$ colors 
and $2$ colors respectively.\\

Wheels can be colored with very few colors as well. A wheel is indeed a cycle
with one extra vertex adjacent to all the vertices in the cycle. 
Therefore we only need one more
color for the extra vertex. Since we need $2$ colors for an even
cycle and $3$ colors for an odd cycle, an even wheel needs
$3$ colors and an odd wheel needs $4$ colors. Therefore, we can
color $W_{13}$ with $4$ colors.\\

The number of colors for $K_{311,222}$ seems to depend on $311$ and $222$.
However, only two colors are needed. Color the set of the $311$ vertices with
one color and the set of the $222$ vertices with a second color. Since no edge
connects two vertices in the same group in a bipartite graph, no two adjacent vertices have the same color. 
In fact, we can extend this result to any $m$ and $n$ in $K_{m,n}$. Therefore,
any complete bipartite graph is 2-colorable.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset3 problem3 spring98
\problem [20 pts]

\bparts 

\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
Exer.\ 38 are isomorphic.

\solution{
The two graphs are isomorphic. Informally, we can see by breaking the graph
into a $K_4$ and a extra vertex with two edges connected to $K_4$.
Therefore, a function $f$ that maps $u_1$ $\rightarrow$ $v_1$, $u_2$ $\rightarrow$ $v_3$,
$u_3$ $\rightarrow$ $v_2$, $u_4$ $\rightarrow$ $v_5$ and $u_5$ $\rightarrow$ $v_4$, is an isomporphism 
between the two graphs. We can verify this since there is an edge between
$u_i$ and $u_j$ iff there is an edge between $f(u_i)$ and $f(u_j)$ for
all $1 \leq i, j \leq 5$. \\
}

\ppart Prove or disprove that the pair of graphs given in Rosen 7.3,
Exer.\ 42 are isomorphic.

\solution{
The two graphs are not isomorphic. Both graphs have two vertices of 
degree 3: $u_2$ and $u_3$ in the first graph and $v_2$ and $v_4$ 
in the second graph.  
Since $u_2$ and $u_3$ are adjacent while $v_2$ and $v_4$ are not,
the two graphs are not isomorphic.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset3 problem4 spring98
\problem [30 pts]

Some properties of a simple graph, $G$, are described below.  For each
property, carefully prove or give a counterexample to the claim that the
property is {\em invariant under isomorphism} ({\em cf.} Rosen, p.455).

\bparts
\ppart
$G$ has an even number of vertices.

\solution{
It is invariant under isomorphism. There must be an one-to-one and onto
mapping between the vertices of two isomorphic graphs. Therefore, the number 
of vertices in the two graphs must be
the same. If one graph has even number of vertices, then the other must
have even number of vertices.
}

\ppart
None of the vertices of $G$ is an even integer.

\solution{
It is not invariant under isomorphism. We do not really care what the 
vertices are. Vertices can be any kind of mathematical objects. 
All we are interested is that whether there
exists a one-to-one and onto function $f$ mapping from vertices of one graph 
to vertices of another with the property that $a$ and $b$ are adjacent in the
first graph if and only if $f(a)$ and $f(b)$ are adjacent in the  second
graph, for all $a$ and $b$ in the first graph. \\

So, for example, let $G_1$ be a graph with a single vertex, 1, and $G_2$ be
a graph with a single vertex, 2. Obviously the two graphs are isomorphic, but
$G_2$ does not have vertices which are even integers.
}

\ppart
$G$ has a vertex of degree 3.

\solution{
It is invariant under isomorphism.  

Let $G_1, G_2$ be simple graphs and $f:V_1\to V_2$ be an isomorphism
between them.  Suppose $v\in V_1$ has degree 3; we want to show that there
is a vertex of degree 3 in $V_2$.  In fact, we'll show that $f(v)$ has
degree 3.
 
Since $v$ has degree 3, there are exactly 3 vertices adjacent to $v$; say
these are $v_1,v_2,v_3$.  Since $f$ is a bijection, $f(v_1),f(v_2)$ and
$f(v_3)$ are all distinct.  Since there is an edge between $v$ and $v_i$
in $G_1$, the definition of isomrphism implies that there is an edge
between $f(v)$ and $f(v_i)$ for $i=1,2,3$, so the degree of $f(v)$ is at
least 3.
 
We now prove by contradiction that the degree of $f(v)$ is at most 3.
Suppose $f(v)$ had degree $>3$.  This means there is a vertex $w \in V_2$
which is not equal to $f(v_1), f(v_2),$ or $f(v_3)$, but is also adjacent
to $f(v)$.  Since, $f$ is a bijection, there is a vertex $v_4 \in V_1$
such that $f(v_4) = w$ and $v_4 \neq v_i$ for $i=1,2,3$.  Since $w=f(v_4)$
is adjacent to $f(v)$, the definition of isomorphism implies that $v_4$ is
adjacent to $v$, contradicting the fact the $v_1,v_2,v_3$ were exactly the
vertices adjacent to $v$.
}

\ppart
$G$ has exactly one vertex of degree 3.

\solution{
It is invariant under isomorphism.

Prove by contradiction:  Let a graph $G_1$ has exactly one vertex of 
degree $3$ while another graph $G_2$ does not have exactly one vertex of 
degree 3. Suppose the two graphs are isomorphic. If $G_2$ does not have 
a vertex of degree 3, then from part (c), there is a contradiction.
If $G_2$ has more than one vertices of degree 3, then there must
be at least one vertex in $G_2$ of degree 3 which is mapped to 
a vertex of degree $\neq 3$ in $G_1$. Since two vertices of different degrees
are mapped from $G_1$ to $G_2$, using the same argument from part (c),
it reaches a contradiction. Therefore, if $G_1$ has exactly one 
vertex of degree 3 , then $G_2$ must also have exactly one 
vertex of degree 3.
}

\ppart
One of the vertices of $G$ is also an edge of $G$.

\solution{
It is not invariant under isomorphism. 

Let $G_1$ be a graph with three vertices, $1$, $2$ and $\{1,2\}$. There is
only one edge from vertex $1$ to vertex $2$. Therefore, $\{1,2\}$ is a vertex
of $G_1$ and also an edge of $G_1$. 

On the other hand, let $G_2$ be a graph with three vertices,
$7$, $12.1$ and an ordered pair $(1, -3)$(note: these are somewhat
tasteless, but legitimate things to use as vertices). There is only 
one edge from vertex $7$ to vertex $12.1$.
Obviously two graphs are isomorphic; however, $G_2$ does not have 
a vertex which is an edge at the same time. 
Therefore, it is not invariant under isomorphism.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset3 problem5 spring98
\problem [30 pts]

{\bf Definition}:
A simple graph, $G$, has {\em inherited degree $d \geq 0$ }
if and only if\\
(i) every vertex of $G$ has degree $\leq d$, or\\
(ii) there is a vertex $v \in G$ of degree $\leq d$, and the subgraph of
$G$ obtained by removing $v$ has inherited degree $\leq d$.

\bparts
\ppart
Prove that $W_n$ has inherited degree 3.

\solution{
We use the induction on $n$.
Let $P(n)$::= $W_n$ has inherited degree 3.

{\bf Base Case:} $W_3$ has four vertices of degree 3 and it has 
inherited degree 3 by definition (i).

{\bf Inductive Step:} Assume $P(n)$ is true, we need to prove $P(n+1)$.
$W_{n+1}$ has $n+1$ vertices of degree $3$ and $1$ vertex of degree $n+1$.
The graph $G$ obtained by removing a vertex of degree $3$ has $n-2$ vertices
of degree $3$, $2$ vertices of degree $2$ and $1$ vertex of degree $n$.
We can also obtain $G$ by removing a edge between two vertices of degree $3$
in $W_n$. Since $W_n$ has inherited degree 3 by inductive hypothesis and removing an edge
does not increase the degree of vertices, $G$ has inherited degree 3.
Then, by definition (ii), $W_{n+1}$ has inherited degree 3.

Therefore, we prove that $W_n$ has inherited degree 3 for $\forall n \geq 3$. \\

%Since this single vertex graph has
%{\em inherited degree 3}, the graph right before (two verticies)
% has {\em inherited degree 3}. Therefore, by building back the
%$W_n$ up, we conclude that it has {\em inherited degree 3}.\\

%So, the point is that if you can keep removing a vertex with
%degree $\leq d$ until every vertex in the subgraph has 
%degree $\leq d$ then the original graph before the vertices are removed
%has {\em inherited degree d}.\\
}

\ppart
Prove that a tree has inherited degree 1.

\solution{
We use the definition of tree in
Rosen, 8.1: a tree is a connected undirected graph with no simple
circuits.  Also, we only consider trees with a finite number of
vertices.

We need to prove two facts here. First we have to prove that every tree 
with at least two vertices has a leaf (a leaf is a vertex of degree one). 
Then we need to show that the subgraph
constructed by removing one leaf is still a tree.\\

First, let's prove that every tree with at least two vertices has a leaf.
Let $T$ be a tree, and let $P$ be a longest simple path in $T$. 
In a finite graph, a path of length greater than or equal to 
the the number of vertices must visit some vertex more than once.  
So a \emph{simple} path must be shorter than the
number of vertices.  Therefore in any finite graph there must be longest
simple path.  (We're using the Well-ordering principle here, taking the
least element of $\set{\card{V}-k : k \mbox{ is the length of a simple
path}}$.)

Suppose $P = (v_1, v_2 \ldots, v_k)$, we claim that $v_1$ is a leaf.  
For if not, there will be an edge $\{v,v_1\}$ in $T$ where $v \neq v_2$. 
The vertex $v$ cannot occur in $P$, for otherwise this creates a cycle, which 
contradicts that the graph is a tree.
Therefore, $P'=(v, v_1, v_2 \ldots, v_k)$ is also a simple path in the tree 
and $P'$ is longer than $P$. But this is a contradiction  
because we have assumed that  $P$ is the longest path in the tree. 
As a result, a tree with 2 or more vertices has to have a leaf. 

Second, let's prove that the subgraph constructed by removing one leaf
is still a tree. 
From the definition given in the
book (cf. Rosen p531), a tree is a connected undirected graph with no simple
circuits. Removing a leaf from a tree does not create any 
circuit. Also, since the leaf has degree 1, it is not connecting any 
other two vertices in the tree. Therefore, after removing the leaf, no vertices 
get disconnected. In other words, the subgraph is still connected.
%removed is adjacent to only one vertex and
%that leaf can only be connected to the graph via the adjacent vertex, 
%the subgraph is still connected. 
Since the subgraph is a connected undirected 
graph with no simple circuits, it is also a tree.\\

Since every tree has a leaf(vertex with degree 1) and the subgraph
is still a tree after removing a leaf, we can apply the same
method in the previous part to show that a tree has inherited degree 1.
}

\ppart
Prove that if a graph has inherited degree $d$, then it is
$(d+1)$-colorable.

\solution{
We use induction on the number of
vertices in a graph to prove this fact. 

Let $P(n)$::= ``$\forall d>0$, any $n$-vertex graphs with inherited degree $d$ is $(d+1)$ colorable.''  

{\bf Base Case}: $n=1$. There is only one 1-vertex graph. And it is obviously
$(d+1)$ colorable ($\forall d>0$).

{\bf Inductive Step:} Assume that $P(n)$ is true, we need to 
prove $P(n+1)$ is true. Given any $(n+1)$-vertex graph $G$ with inherited degree $d$ for any $d>0$, 
there are 2 possible cases: 
\begin{enumerate}
\item All vertices in $G$ has degree $\leq d$. Then it is $(d+1)$-colorable,
as proved in the lecture.
\item There is a vertex $v\in G$ of degree $\leq d$, and the subgraph
$G'$ obtained by removing $v$ has inherited degree $d$. Since $G'$
has $n$ nodes and has inherited degree $d$, by inductive hypothesis $G'$ is 
$(d+1)$ colorable. Now consider the vertex $v$. Since it has degree $\leq d$,
it has at most $d$ neighbors and therefore it can be colored with the $(d+1)^{st}$ color 
which is different from all of its neighbors.
\end{enumerate}

Therefore, by induction, every graph with inherited degree $d$ is $(d+1)$-colorable.\\
%following method to color a graph with inherited degree $d$.
%Let's remove a vertex with degree $\leq d$ until we have every 
%vertices have the degrees $\leq d$.
%Then, we can easily show that every graph with all the vertices with
%degree $\leq d$ can be colored with $d+1$ colors by induction.\\
%The base case is a graph with one vertex. It is true since only one
%color is needed. For induction step, 
%let's consider a graph $G_{n+1}$ with $n+1$ vertices of degree $\leq d$.
%Let's remove a vertex from $G$ and let say the remaining graph is $G_n$.
%Since we are not increasing the degree of any vertex by removing a vertex,
%all the vertices in $G_n$ have the degrees $\leq d$. So, by inductive
%hypothesis, we can color $G_n$ with $d+1$ colors. Now, let's put the
%vertex we took out back to the graph. Since that vertex can be adjacent
%to at most $d$ other vertices, we can color it with one remaining color.
%Therefore, we proved that every graph with all the vertices with degree
%$\leq d$ can be colored with $d+1$.\\
%
%Then,  we can keep adding a vertex with degree $\leq d$ to build back 
%the original graph with inherited degree $d$, since we can always 
%assign a (n+1)th color to the added vertex. Therefore,
%Any graph with inherited degree $d$ is (d+1) colorable.\\
}

\ppart
For every $n>0$, describe an example of a graph which does not have
inherited degree n, but which is 2-colorable.

\solution{
An example would be $K_{n+1, n+1}$. Every vertex in $K_{n+1, n+1}$ has
degree $n+1$. Therefore, it does not have inherited degree $n$.
However, it is $2$-colorable since every complete bipartite graph is $2$-colorable.
}

\eparts

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  Problem Set 4    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \problem
% digraphs, path counting and matrices
%Rosen 7.4, problem 11 but change the graph in Exercise 2 at least a
%little (because problem 11 has a solution in the back of Rosen).
%Type in the new problem.
%Also, we don't need 6 parts---maybe just three, the number of paths of
%length 3, 5, and 7

Find the number of paths of length 5 from a to e of in the directed graph shown below
\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\arabic{enumii})}
%% \begin{enumerate}
%% \item of length 2
%% \item of length 3
%% \item of length 5
%% \end{enumerate}

\begin{center}
\epsfxsize=4in
\epsfbox{figures/ps4p2.eps}
\end{center}



\solution{
\medskip
\textbf{Solution:}\\

%% \begin{enumerate}

%% \item 
%% \begin{enumerate}
%% \item a-b  b-a
%% \end{enumerate}

%% \item 
%% \begin{enumerate}
%% \item a-e e-a a-e
%% \item a-b b-c c-e
%% \item a-d d-b b-e
%% \end{enumerate}

%% \item
\begin{enumerate}
\item a-b b-e e-a a-b b-e
\item a-b b-c c-e e-a a-e
\item a-e e-a a-e e-a a-e
\item a-e e-a a-b b-c c-e
\item a-e e-a a-d d-b b-e
\item a-d d-b b-e e-a a-c
%% \item a-b b-c c-d d-b b-e
\end{enumerate}

%% \end{enumerate}

}  
%% end solution
               
%%%%%%%%%%%%%%  Fall 2000  Problem Set 4    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \problem
% Digraphs
An {\em Euler path\/} in a digraph $G$ is a path that traverses all the
edges of $G$, each edge exactly once.  Unlike an Euler circuit, it
need not end up at the same vertex where it started.

Say whether each of the following digraphs has an Euler path, an
Euler circuit, both, or neither.
Justify your answers by exhibiting the circuits and paths that you say
exist, and proving that the others don't exist.


%[[[Put the actual graphs here, without giving them the citation from
%Rosen.]]]

%\bparts

%\ppart
\begin{enumerate}
\item
\epsfxsize=2in
\epsfbox{figures/ps4p3fig1.eps}
%\caption{Digraph a}
%[[[Digraph from Rosen section 7.5 ex. 24]]]

%\ppart
%% \item
%% \epsfxsize=2in
%% \epsfbox{figures/ps4p3fig2.eps}
% \caption{Digraph b}
% [[[Digraph from Rosen section 7.5 ex. 26]]]

%\ppart
\item
\epsfxsize=2in
\epsfbox{figures/ps4p3fig3.eps}
%\caption{Digraph c}

%[[[Digraph from Rosen section 7.5 ex. 28]]]
%\eparts
\end{enumerate}


\solution{
\medskip
\textbf{Solution:}\\

\begin{enumerate}

 
\item 
\begin{description}
\item[Euler Circuit] NO, because vertex $a$ has in-degree 1 and out-degree 2
\item[Euler Path] YES. Since it doesn't have an Euler Circuit and exactly 2 vertices have odd degree (i.e. $a$, $d$). E.g: $a,b,d,b,c,d,c,a,d$
\end{description}

%% \item
%% \begin{description}
%% \item[Euler Circuit] YES. One is: $a,d,b,d,e,b,e,c,b,a$
%% \item[Euler Path] YES. Since it has an Euler Circuit, it has an Euler path. The example above works here too.
%% \end{description}

\item
\begin{description}
\item[Euler Circuit] YES. E.g.: $a,b,c,e, b,d,c,b,f,d,e,f,e,a,f,a$
\item[Euler Path] YES. If a graph has an Euler Circuit, then it also
has an Euler path.  
\end{description} 

\end{enumerate}

  }
                     
%%%%%%%%%%%%%%  Fall 2000 Problem Set 4     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \problem
% graph coloring
For each of the following graphs, 
\begin{itemize}
\item Find the chromatic number
\item Say whether it is possible to decrease the chromatic number by removing a single vertex and all edges incident with it.
\end{itemize}

Justify your answers.
\bparts
\ppart
The graph in Rosen Section 7.8, exercise 4.
%% \ppart
%% The graph in Rosen Section 7.8, exercise 6.
\ppart
The graph in Rosen Section 7.8, exercise 8.
\eparts
%[[[George:  You might want to reduce this, e.g., to 2 parts instead
%of 3.]]]


\solution{
\medskip
\textbf{Solution:}\\
\begin{enumerate}
\item Since there is a triangle, at least 3 colors are needed. To show that 3 colors suffice, notice that we can color the vertices around the outside alternately using red and blue, and color vertex $g$ green.

If we remove vertex $g$, the chromatic number will be reduced to 2. We can color vertices $f,b,d$ blue and $a,c$ and $e$ red

%% \item Since there is a triangle, at least 3 colors are needed. The coloring in which $b$ and $c$ are blue, $a$ and $f$ are red, and $d$ and $e$ are green shows that 3 colors suffice. 

Even if we remove a vertex, at least one of the two triangles $ace$ and $bdf$ must remain since they share no vertices. Therefore, the smaller graph will still have chromatic number 3. 

\item Since vertices $b,c,h,i$ form a $K_{4}$, at least 4 colors are needed. A coloring using only 4 colors is indeed possible: eg: let $a$ and $c$ be red, $b,d$ and $f$ blue,: $g$ and $i$ green and $e$ and $h$ yellow.

If we remove vertex $h$ and recolor vertex $e$ red, then we can eliminate color yellow from the solution, thus reducing the chromatic number to 3. 

\end{enumerate}
  }


             
%%%%%%%%%%%%%%  Fall 2000  Problem Set 4    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem

Rosen section 7.5, exercise 44.


\solution{
\medskip
\textbf{Solution:}\\

This graph has no Hamiltonian circuit. If it did, then certainly the circuit would have to contain edges ${d, a}$ and ${a,b}$, since these are the only edges incident to vertex $a$. By the same reasoning, the circuit would have to contain the other six edges around the outside of the figure. These eight edges already complete a circuit, and this circuit omits the nine vertices on the inside. Therefore there is no Hamiltonian circuit.


  }

\problem
% trees
%Rosen section 8.1, exercise 18
Either describe what a full $m$-ary tree with $76$ leaves and height $3$, where
$m$ is a positive integer, would look like, or show that no such tree exists.


\solution{
\medskip
\textbf{Solution:}\\
 

Such a tree does exist. We first note that such a tree  must have $i=\frac{75}{m-1}$ internal vertices. This has to be a whole number, so $m-1$ must divide $75$. This is possible, for example when $m=6$. Let's try to construct such a tree: A complete $6$-ary tree of height $2$ would have $36$ leaves. We therefore need to add $40$ leaves. This can be accomplished by changing $8$ vertices at level $2$ to internal vertices; each such change adds 5 leaves to the tree ($6$ new leaves at level $3$, minus the one leaf at level 2 that has been changed to an internal vertex). So the tree looks like this:
The root has $6$ children, each of which has $6$ children, giving $36$ vertices at level $2$. Of these, $28$ are leaves and each of the remaining $8$ vertices at level $2$ has $6$ children living at level 3, for a total of $48$ leaves at level $3.$ The total number of leaves is thus $48+28=76$, as desired.

  }    
%%%%%%%%%%%%%%  Fall 2000  Problem Set 4   %%%%%
 \problem 
% trees
 
Rosen 8.2 exercise 8.  How many weighings of a balanced scale are
needed in order to find a counterfeit coin among eight coins if the
the counterfeit coin is either heavier or lighter than the others?
Describe an algorithm to find the counterfeit coin using this number
of weighings.  

\solution{
\medskip
\textbf{Solution:}\\
 
Decision tree theory applied naively says that at least $log_{3}8=2$ weighings are needed, but in fact at least 3 weighings are needed. To see this, consider what the first weighing might accomplish. We can put one, two or three coins in each pan. If we put one in each pan, and the scale balances, what we know is that the counterfeit must be among the remaining 6. Similarly, if we put 2 and the scale balances, we narrow down our list of suspects to the remaining 4. If we put 3 in each pan and the scale balances, we are in really good shape, but what if it doesn't? Then our list of suspects will be the 6 coins in the scale. What this means is that however many coins we choose to put on each pan (1,2 or 3), there's always a case where the list of suspects after the first weighing will be $\geq 4$. One weighing is not enough to distinguish the counterfeit from among a list of 4 suspects.


 In Tutorial 1, we showed that we can solve a bigger problem (12 coins) with three weighings, so we should be able to solve this one with the same number of weighings. So if we are lazy and we want to just use the algorithm we came up with in Tutorial, we just add 4 good coins to our collection and apply that algorithm. 

However, a simpler solution is available: Put two coins in each pan. If the scale balances, then the search is reduced to the other four coins. If the scale does not balance, then the counterfeit is among the four coins on the scale. In both cases, after 1 weighing we have cut down our list of suspects to 4. Call them A, B, C, D. First compare coins A and B. If they balance, then the counterfeit must be among the other 2. In this case, compare C with A (which we now know must be good). If they balance, then D is counterfeit. If not, C is counterfeit. On the other hand, if A and B do not balance, then one of them is the counterfeit. Compare A with C (which we know must be good). If they balance, B is the counterfeit. If they do not, A is the counterfeit.  
 }
%%%%%%%%%%%%%%%%spring 01 tutorial 4 %%%%%%%%%%%%%%%%5
\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp!]
    %graphic is from  /a/class/6.042/spring00/archive/lectures/
 \centerline{\resizebox{!}{2.0in}{\includegraphics{dag}}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

\problempart What's the length of a critical path; find such a path.

\solution{
\medskip
\textbf{Solution:}\\
The sequence 18.01, 18.03, 6.002, 6.004, 6.033, 6.857 constitutes
a critical path since it is the longest directed path in the graph.}

\problempart How many terms are necessary and sufficient to complete
all of the courses in Figure~\ref{fig:dag}, assuming prerequisites are
observed, but course load is no issue? Prove your answer (both
necessary and sufficient).

\solution{
\medskip
\textbf{Solution:}\\
The answer is suggested by the way Figure~\ref{fig:dag} is drawn---each
horizontal row is an antichain.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms. Furthermore, since there is a critical path of length six,
there is no way to finish in less than six terms.}
                                                     
%%%%%%%spring 01 tutorial 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}

\solution{
\medskip
\textbf{Solution:}\\
\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}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

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


\solution{
\medskip
\textbf{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$.

   }


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

\solution{
\medskip
\textbf{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{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}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\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}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not a line graph.}


\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$.''

\solution{
\medskip
\textbf{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.
 
  }  \eparts      
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5










%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
% FALL 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GNERAL GRAPHS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
pset 4, #3
\problem \textbf{Edges and Vertices}

Do \S 7.2, Exercise 26 (part a) from the Rosen textbook.

\solution{
We want to show that $2 e\ge v m$. We know from Theorem 1 (Rosen)
that $2 e$ is the sum of the degrees of the vertices. This certainly cannot 
be less than the sum of $m$ for each vertex, since each degree is no less
than $m$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 4, #4
\problem \textbf{Bipartite Graphs}

Do \S 7.2, Exercise 36 from the Rosen textbook.

\solution{
Suppose the parts are of size $k$ and $v-k$. Then the maximum number of
edges the graph may have is $k(v-k)$ (an edge between each pair of 
vertices in different parts). By algebra of calculus, we know that the 
function $f(k)=k(v-k)$ schieves its maximum when $k=v/2$, giving 
$f(k)=v^2/4$. Thus there are at most $v^2/4$ edges.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 4, #5
\problem \textbf{Isomorphism}

\begin{problemparts}

\problempart Do \S 7.3, Exercise 36 from the Rosen textbook.

\solution{
These graphs are not isomorphic. The second has a vertex of degree 4,
whereas the first does not.
}

\problempart Do \S 7.3, Exercise 38 from the Rosen textbook.

\solution{
These two graphs are isomorphic. Each consists of a $K_4$ with a fifth vertex
adjacent to two of the vertices in the $K_4$. Many isomorphisms are possible.
One is $f(u_1)=v_1$, $f(u_2)=v_3$, $f(u_3)=v_2$, $f(u_4)=v_5$, and 
$f(u_5)=v_4$.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pset 4, #6

\problem \textbf{Connectivity}

% Spring 95 Quiz 1
The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 
Prove that if $G$ is not connected then $G^c$ is.

\solution{
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $G^c$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $E^c$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $G^c$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $G^c$ is connected.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 6, #3
\problem \textbf{The Touring Knight} \\
%% Remove the Rosen cite, since the last problem is an odd exercise %%
A knight is a chess piece that can move either two spaces horizontally
and one space vertically or one space horizontally and two spaces
vertically.  That is, a knight on square $(x, y)$ can move to any of the
eight squares $(x \pm 2, y \pm 1), (x \pm 1, y \pm 2)$, if these squares
exist on the chessboard (which is normally 8 $\times$ 8).

A knight's tour is a sequence of legal moves by a knight starting at
some square and visiting each square exactly once.  A knight's tour is
called reentrant if there is a legal move that takes the knight from
the last square of the tour back to where the tour began.  We can
model knight's tours using the graph that has a vertex for each square
on the board,with an edge connecting two vertices if a knight can
legally move between the squares represented by these vertices.
\begin{problemparts}

\problempart 
Show that finding a reentrant knight's tour on an $m
\times n$ chessboard is equivalent to finding a Hamilton circuit on
the corresponding graph. 

\solution{In a Hamiltonian circuit, we need to visit each vertex once
moving along the edges and returning to the starting point. A
reentrant knight's tour is precisely such a circuit, since we visit
each square once, making legal moves, and return to the starting
point.}

\problempart 
Show that the graph representing the legal moves of a
knight on a $m \times n$ chessboard, wherever $m$ and $n$ are
positive integers, is bipartite.

\solution{Each square of the board can be thought of as a pair of
integers $(x,y)$. Let $A$ be the set of squares for which $x+y$ is
odd, and let $B$ be the set of square for which $x+y$ is even. This
partitions the vertex set of the graph representing the legal moves of
a knight on the board into two parts. Now every move of the knight
changes $x+y$ by an odd number -- either $1+2=3$, $2-1=1$, $1-2=-1$,
or $-1-2=-3$. Therefore every edge in this graph joins a vertex in $A$
to a vertex in $B$. Thus the graph is bipartite.}

\problempart Deduce that there is no reentrant knight's tour on an $m
\times n$ chessboard when $m$ and $n$ are both odd. (\emph{Hint:}
Problem Set 4, problem 7.)

\solution{Since there are $mn$ squares on the $m \times n$ board, if
both $m$ and $n$ are odd, there are an odd number of squares. Since by
part (b), the corresponding graph is bipartite, from PS 4, problem 7,
we know that it has no cycle of odd length, \emph{i.e.} it has no
Hamilton circuit (since there are an odd number of nodes). Hence,
there is no reentrant knight's tour.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 6, #5
\problem \textbf{Euler Circuits} \\ Show that a
directed multigraph having no isolated vertices has an Eulerian
circuit if and only if the graph is weakly connected and the in-degree
and out-degree of each vertex are equal.

\solution{First suppose that the directed multigraph has an Euler
circuit. Since the circuit provides a path from every vertex to every
other vertex, the graph must be strongly connected (and hence also
weakly connected). Also, we can count the in-degrees and out-degrees
of the vertices by following the circuit; as the circuit passes
through a vertex, it adds one to the count of both the in-degree (as
it comes in) and the out degree (as it leaves). Therefore the two
degrees are equal for each vertex. Conversely, suppose that the graph
meets the conditions stated. Then we can proceed as in the proof of
Theorem 1 (Rosen p.478) and construct an Euler circuit. }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PATHS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 9, #1
\begin{problems}

\problem We consider simple graphs with $n$ distinctly labeled vertices.

\bparts
\ppart 
How many complete graphs are there on these $n$ vertices?

\solution{One.}

\ppart How many simple paths\footnote{We use the definition of simple path
from the notes: a path with no repeated vertex.}
of length $i$ are there in the complete graph
with $n$ vertices?

\solution{

A path is determined by the order in which vertices occur.  In the
complete graph all vertices are connected by an edge.  A path of length
$i$ has $i$ edges and $i+1$ vertices, so the number of simple paths of
length $i$ ($0 \leq i < n$), is the same as the number of
$(i+1)$-permutations of the $n$ vertices , namely, $P(n,i+1) \eqdef
n!/(n-(i+1))!$.

}

\ppart How many simple \emph{cycles} of length $i$ are there in the
complete graph?  (A simple cycle is a ``circular'' simple
path.)

\solution{

The length and number of vertices on a simple cycle are the same, so each
simple cycle can be represented by the unique sequence of $i$ vertices on
it, starting at some vertex and picking a direction to go around the
cycle.  There are $i$ vertices at which to start and two choices of
direction, so each cycle can be represented by exactly $i \cdot 2$ of the
$P(n,i)$ vertex sequences of length $i$.  Hence the number of simple
cycles of length $i$ is $P(n,i)/2i$.

}

\ppart
How many such distinctly labelled $n$-vertex graphs are there?

\solution{

$2^{\binom{n}{2}}$.  For each possible edge, we choose whether it's in the
graph or not.

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 9, #4
\problem \textbf{Pascal's Triangle.  }

Let us redraw Pascal's Triangle in the following way:

\begin{center}
\begin{tabular}{lcccccccc}
$1$ \\
$1$ & $1$ \\
$1$ & $2$ & $1$ \\
$1$ & $3$ & $3$ & $1$ \\
$1$ & $4$ & $6$ & $4$ & $1$ \\
$1$ & $5$ & $10$ & $10$ & $5$ & $1$ \\
$1$ & $6$ & $15$ & $20$ & $15$ & $6$ & $1$ \\
$\cdot$ & $\cdot$ & $\cdot$ & $\cdot$ & $\cdot$& $\cdot$  & $\cdot$ & $\cdot$ \\
\end{tabular}
\end{center}

Now let n be a nonnegative integer and let k be an integer with $0
\leq k \leq n$.  Define $path(n,k)$ to be the number of paths from the
top left corner (the entry $\binom{0}{0} = 1 $) to the entry
$\binom{n}{k}$, where each path is composed of only two possible types of
moves: 

type $(a)$: from any entry in the Triangle we can move to the entry immediately below the current entry (i.e. in the next row) 

type $(b)$: from any entry in the Triangle we can move to the entry
immediately below and to the right of the current entry (i.e. in the next row).

 We define $path(0,0)=1$.  Prove that the value of an entry 
$\binom{n}{k}$ of Pascal's
triangle represents $path(n,k)$, the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.

\solution {
Notice that $path(n,0)=1$, (we must move straight down to reach $\binom{n}{0}$) and $p(n,n)=1$, (we must move diagonally to reach $\binom{n}{n}$).

Observe that each path from $\binom{0}{0}$ to $\binom{n}{k}$ is either

(i) a path from $\binom{0}{0}$ to $\binom{n-1}{k}$ followed by one vertical move $(a)$, or 

(ii) a path from $\binom{0}{0}$ to $\binom{n-1}{k-1}$ followed by one diagonal move $(b)$.

So, the total number of paths 
is $path(n,k) = path(n-1,k)+path(n-1,k-1)$.
The numbers $path(n,k)$
are computed in exactly the same way as the binomial coefficients
$\binom{n}{k}$ starting with the same initial values.  Hence it
follows that for all integers n and k with $0 \leq k \leq n$, \[
path(n,k) = \binom{n}{k}\] Thus the value of an entry $\binom{n}{k}$ of
Pascal's triangle represents the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.  And, we
have derived another combinatorial interpretation of the numbers $\binom{n}{k}$.  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 9, #6

\problem
You are at point $(0,0,0)$ in three-dimensional space, and you need to get to 
point $(i,j,k)$. You can only make unit-length moves parallel
to three coordinate axes, and only moves that get you closer to
your goal. How many different paths can you take?

\solution{
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$
steps.  Of these steps, $i$ must be along one dimension, $j$ must be
along another, and $k$ must be along the third.  The question becomes
how to distribute the three types of steps amongst the $i+j+k$ total
steps.  There are $\binom{i+j+k}{i}$ ways to choose which of the
$i+j+k$ steps will be along the first dimension, $\binom{j+k}{j}$
ways to choose which of the $j+k$ remaining steps will be along the
second dimension, and ${\binom{k}{k}} = 1$ way to choose which of the
$k$ remaining steps will be along the third dimension.  By the product
rule, the total number of different paths is ${\binom{i+j+k}{i}}
{\binom{j+k}{j}}$.

Alternatively, you could argue as follows:
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$ steps.  Of
these steps, $i$ must be along one dimension, $j$ must be along
another, and $k$
must be along a third.  The question becomes how to arrange these steps in
order.  This can be done in $\binom{i+j+k}{i, j, k}$ ways.  (Consult the 
multinomial definition for the factorial form of this.)
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GRAPH COLORING%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset #8 #5
\problem \textbf{Coloring}

There are 4 people looking for companies to work for: Alice, Bob, 
Chris, and Dave.  Alice refuses to work for the same company as any of 
the guys.  Dave also doesnt want to work for the same company as any 
of the other people. 

\bparts

\ppart How could you represent the constraints on who is willing to
work with other people as a graph coloring problem ?

\solution{
This can be represented as a graph with nodes representing
the people, and edges representing people who do not want to work
together. Namely, there is an edge between Alice and every one else
and between Dave and every one else. 
Assigning a color to a node would correspond to assigning
a company to a person. 
Recall that a legal graph coloring does
not allow edges to connect nodes of same color, thus a legal coloring
of the graph would imply an assignment of people to jobs respecting
their wishes. 
Thus your graph could look like :

\begin{figure}[h]
\centerline{\resizebox{!}{1.5in}{\includegraphics{H58-p5.eps}}}
\end{figure}
}
\ppart How many ways from $n$ possible companies(where $n >=4$ and
more than one person can work for each company) can these people work
and still be happy ?

\solution{
To solve the problem, all that remains is to figure out is
the possible colorings of the graph that exist. 
There are 4 nodes, thus it is possible for the graph to be
colored with 4 separate colors.  In other words, assign a 
different company to each person.  The number of
ways to assign 4 colors to the nodes from n possible
colors, is equal to the number of 4-permutations of the n colors
which equals P(n,4) = n!/(n-4)!

The graph can also be colored with 3 colors.  This is because
there is no edge connecting nodes Bob and Chris, and therefore they may be
colored the same color.  Thus, the number of ways to color the
graph with 3 colors, from $n$ possible colors equals $P(n,3)=n!/(n-3)!$.

The graph can not be colored with fewer colors due to the constraints
represented by the edges, in addition it cannot be colored with more than
4 colors, since there are only 4 nodes.  Thus the total possible assignments
of companies equals
P(n,4) + P(n,3) = n!/(n-4)! + n!/(n-3)! = (n)(n-1)(n-2)(n-2).
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 4, #7
\problem \textbf{Graph Coloring}

Argue that a graph is 2-colorable if and only if every simple cycle is of
even length.

\solution{
Assume a graph has a simple cycle of odd length.
Let the cycle be $v_1,v_2,\ldots, v_n,v_1$, where $n$ is odd. Suppose that
two colors (red and blue) sufficed to color the graph containing this circuit.
Without loss of generality let the color of $v_1$ be red. Then $v_2$ must 
be blue, $v_3$ must be red, and so on, until finally $v_n$ must be red (since
$n$ is odd). But this is a contradiction, since $v_n$ is adjacent to $v_1$.
Therefore at least three colors are needed. Hence a graph is 2-colorable only
if every simple cycle is of even length. Conversely, assume the graph has
no simple cycle of odd length. We show that it is possible to color the
graph using two colors. Without loss of generality, assume that the 
graph is connected. (As otherwise we can repeat the argument for each 
connected component of the graph). Select a node, say $m$, in the graph and
color it red. Color all the nodes adjacent to $m$ blue. (Call the set of all
such nodes $S_1$.) Color all the nodes that are adjacent to the nodes in $S_1$
but have not yet been colored, red. (Call the set of all such nodes $S_2$.) 
Continue this process until you have colored all the nodes. We now show that
no two nodes in $S_i$ are connected by an edge, for all $i$.\footnote{This is
sufficient to establish that our coloring is valid, since by construction 
we cannot have two 
adjacent nodes that were colored identically but do not belong to the same set
$S_i$.} Assume that we 
can find two nodes $u$ and $w$ in some set $S_i$ that are adjacent in the
graph. If $u$ and $w$ are adjacent to a node in $S_{i-1}$ then we have a 
simple cycle of length $3$, which is impossible. 
So let $u_{i-1}\neq w_{i-1} \in S_{i-1}$
be nodes adjacent to $u$ and $w$ respectively. 
Now if $u_{i-1}$ and $w_{i-1}$ are
adjacent to a single node in $S_{i-2}$, say $c$, 
then $u,u_{i-1},c,w_{i-1},w,u$ is a 
simple cycle of length 5, which is impossible. 
So let $u_{i-2}\neq w_{i-2}\in S_{i-2}$ be nodes adjacent to 
$u_{i-1}$, and $w_{i-1}$ 
respectively. Continuing this way we arrive
at nodes $u_1\neq w_1 \in S_1$. However these are adjacent to $m$.
But this gives us a simple cycle 
$m,u_1,u_2,\ldots,u_{i-1},u,w,w_{i-1},w_{i-2}\dots,w_1,m$, where 
$u_j,w_j\in S_j$. But
this cyle has length $2 i+1$, which is odd, hence a contradiction. Therefore,
for all $i$ we do not have two nodes in $S_i$ that are connected by an edge. 
Therefore our coloring is valid.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TREES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 5, #4
\problem \textbf{Decision Trees} \\ How many weighings
of a balance scale are needed to find a counterfeit coin among 8 coins
if the counterfeit coin is either heavier or lighter than the others?

\solution{
Decision tree theory applied naively say that at least
$\lceil \log_3 8 \rceil = 2$ weighings are needed, but in fact at least
3 weighings are needed. To see this, consider what the first weighing
might accomplish. We can put 1, 2, or 3 coins in each pan for the
first weighing (no other arrangement will yield any information at
all). If we put on or two coins in each pan, and if the scale
balances, then we only know that the counterfeit is among the six or
four remaining coins. If we put 3 coins in each pan and if the scale
does not balance, then essentially all we know is that the counterfeit
coin is among the six coins involved in the weighing. In every case,
we have narrowed the search to more than 3 coins, so one more weighing
cannot find the counterfeit (there being only three possible outcomes
of one more weighing). }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 5. #6
\problem \textbf{Rooted Spanning Trees} \\
A \textbf{directed, rooted spanning tree} of a digraph is a
rooted tree whose edges are from the digraph with the property 
that every vertex of
the digraph is reachable by a directed path from the root of the tree.
Show that
a connected directed graph in which each vertex has the same in-degree
and out-degree has a rooted spanning tree. (\emph{Hint:} Use an Euler
circuit.)

\solution{By the previous problem, there is an Euler circuit in the
directed graph. We follow $C$ and delete from the directed graph every
edge whose terminal vertex has been previously visited in $C$. We
claim that the edges that remain in $C$ form a rooted tree. Certainly,
there is a directed path from the root to every other vertex, since we
only deleted edges that allowed us to reach vertices we could already
reach. Furthermore, there can be no simple circuits, since we removed
every edge that would have completed a simple circuit.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 5, #7

\problem \textbf{Triangle Inequality} \\ 
Let $T_1$ and $T_2$ be spanning trees of a graph. The
\textbf{distance} between $T_1$ and $T_2$ is the number of edges in
$T_1$ and $T_2$ that are not common to $T_1$ and $T_2$. Suppose that
$T_1, T_2$ and $T_3$ are spanning trees of the simple graph $G$. Show
that the distance between $T_1$ and $T_3$ does not exceed the sum of
the distance between $T_1$ and $T_2$ and the distance between $T_2$
and $T_3$.

\solution{Suppose that $T_1$ contains $a$ edges that are not in $T_2$,
so that the distance between $T_1$ and $T_2$ is $2a$. Suppose that
$T_2$ contains $b$ edges that are not in $T_3$, so the distance
between $T_2$ and $T_3$ is $2b$. Now at worst, the only edges that are
in $T_1$ and not in $T_3$ are those $a+b$ edges that are in $T_1$ and
not in $T_2$, or in $T_1$ and $T_2$ but not in $T_3$. Therefore the
distance between $T_1$ and $T_3$ is at most $2(a+b)$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 5, #8
\problem
\textbf{Minimum Spanning Trees} \\
A minimum spanning tree in a connected weighted graph $G$ is a
spanning tree in $G$ with the property that no other spanning tree in
$G$ has a lower total weight. Show that an edge with smallest weight
in a connected weighted graph must be part of any minimum spanning
tree.

\solution{
Suppose that an edge $e$ with smallest weight is not included in some
minimal spanning tree; in other words, suppose that the minimum
spanning tree $T$ contains only edges with weights larger than that of
$e$. If we add $e$ to $T$, then we will obtain a graph with exactly
one simple circuit, which contians $e$. We can then delete some other
edge in the circuit, resulting in a spanning tree with weight strictly
less than that of $T$ (since all the other edges have larger weight
than $e$ has). This is a contradiction to the fact that $T$ is a
minimum spanning tree. Therefore, an edge with smallest weight must be
included in $T$.}

%END   Tina's problems

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------
% source: pset fall00
% topic: structural induction, strings, proofs
% last used: karger s01 pset3
% Added by Jaime

\problem We define the family $\T$ of number search trees as follows:
\begin{enumerate}
\item
  Any single number $x$ is in $\T$.
\item If $T$ is in $\T$, and $x$ is a number greater than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``left'' from $x$ to $T$ is also in $\T$.
n\item If $T$ is in $\T$, and $x$ is a number smaller than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``right'' from $x$ to $T$ is also in $\T$.
\item If $T$ and $T'$ are in $\T$, and a number $x$ is larger than
  every number in $T$ but smaller than every number in $T'$, then the
  structure formed by attaching an arrow labelled ``left'' from $x$
  to $T$ and an arrow labelled ``right'' from $x$ to $T'$ is also in
  $\T$.
\end{enumerate}
In all cases above, the number $x$ is called the \emph{root} of the
tree that is formed.  Since the descriptions above are wordy, you may
wish to introduce some notation, like makeleft$(T,x)$ to denote the
thing built up according to the first recursive rule.  Likewise,
makeright$(x,T)$, makeboth$(T,x,T')$.

\ppart How many different number search trees with four nodes will be
in $\T$ if our domain consists of the numbers 1, 2, 3 and 4?  Give an
example of how one such tree might be constructed using the structural
definition.

\solnospace{Consider the number search tree with each number at the
root.  If 1 is at the root, 2, 3 and 4 must be to its right.  There
are five different number search trees that can be made with 2, 3 and
4, so there are three different trees that can be made with 1 at the
root.  If 2 is at the root, 1 must be to its left, and 3 and 4 to its
right.  Since there are two different number search trees that can be
made with 3 and 4, there are two different trees that can be made with
2 at the root.  When 3 is at the root, the case is very similar to 2,
and when 4 is at the root, the case is very similar to 1.  This means
there are 14 number search trees that can be made containing all of
the numbers 1, 2, 3 and 4.
\begin{center}
\begin{picture}(60,80)
\put(7,45){1}
\put(10,40){\circle*{3}} \put(10,40){\line(1,1){20}}
\put(27,65){2}
\put(30,60){\circle*{3}} \put(30,60){\line(1,-1){20}}
\put(47,45){4}
\put(50,40){\circle*{3}} \put(50,40){\line(-1,-2){10}}
\put(30,20){3}
\put(40,20){\circle*{3}}
%\put(10,40){\circle*{3}} %\put(10,40){\line(2,3){20}}
%\put(30,10){\circle*{3}}
\end{picture}\\
An example of a number search tree for the numbers 1, 2, 3 and 4.
\end{center}
}

Now consider the following recursive algorithm for checking whether a
certain number is present in a tree $T$.
\begin{tabbing}
else\=else\=else\=else\=\kill

Algorithm Member$(q,T)$\\
\\
\>Let $x$ be the root of tree $T$\\
\> {\bf if} $x=q$ {\bf then}\\
\> \> {\bf return} YES\\
\> {\bf else} \\
\> \> {\bf if} $q<x$ {\bf and} $x$ has a ``left'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else if} $q>x$ {\bf and} $x$ has a ``right'' arrow to tree $T'$ 
{\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else}\\
\> \> \> {\bf return} NO\\
\end{tabbing}

\ppart Prove that a call to member$(q,T)$ returns YES if and only if
$q$ is a number in the number search tree $T$.

\newcommand{\membern}{\hbox{member}}
\newcommand{\makeleft}{\hbox{makeleft}}
\newcommand{\makeright}{\hbox{makeright}}
\newcommand{\makeboth}{\hbox{makeboth}}

\solution{ We use structural induction. We use $x<T$ to mean
  $x<\mbox{all numbers in }T$, and define $x>T$ similarly. We get four
  cases, one for each production rule.
\begin{enumerate}
\item
For a single-node tree $T$ with root $x$, if $q\in T$, $q=x$ and 
$\hbox{member}(q,T)$ returns YES. If $q\notin T$, since there are no 
arrows
from $x$, the final else is taken and $\hbox{member}(q,T)$ returns NO.
\item
Fix $T$, and assume $\forall q$, $\hbox{member}(q,T)$ returns YES iff 
$q\in T$.
We need to show that $\forall q,\forall x>T$,
$\membern(q,\makeleft(T,x))$ returns YES iff $q\in\makeleft(T,x)$.
If $q\in\makeleft(T,x)$, $q=x$ or $q\in T$. If $q=x$,
$\membern(q,\makeleft(T,x))$ immediately returns YES. If $q\in T$, $q<x$
and since $x$ has a left arrow to $T$, $\membern(q,T)$ is returned,
which is YES by inductive assumption. If $q\notin\makeleft(T,x)$, then
$q\ne x$ and $q\notin T$, so either the final else is taken and NO
returned or $\membern(q,T)$ is returned, returning NO by inductive
assumption.
\item
Similar to 2.
\item
Fix $T$, $T'$ and assume $\forall q$, $\membern(q,T)$ returns YES iff
$q\in T$ and $\membern(q,T')$ returns YES iff $q\in T'$. We need to
show that $\forall q$, $\forall x\suchthat x>T\wedge x<T'$,
$\membern(q,\makeboth(T,x,T'))$ returns YES iff
$q\in\makeboth(T,x,T')$. If $q\in\makeboth(T,x,T')$, there are 3
cases. Case 1: $q=x$, so member returns YES. Case 2: $q\in T$, so
$q<x$, $x$ has a left arrow to $T$, and $\membern(q,T)$ is returned,
which is YES by inductive assumption. Case 3: $q\in T'$, by similar
reasoning YES is returned. If $q\notin\makeboth(T,x,T')$, then $q\ne
x$, $q\notin T$, and $q\notin T'$, so either NO is returned
immediately or $\membern(q,T)$ or $\membern(q,T')$ is returned, which
are NO by inductive assumption.
\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------
% source: spring 99, pset 3
% topic: structural induction, list
% last used: karger spring 01 tut3

%\ignore'd by Joe 2/18--this could be a good problem
%but I think needs reworking. If we really want to make
%it correspond to the ``structural induction'' and recurs. structure
%definition stuff then the definition of the game tree should be more 
%formal with base cases and combination rules. Also, the way it's
%described now, since nodes correspond to situations in the game,
%it is a directed graph, not a tree.

\problem Many two-person games in which players alternate moves---like
chess, checkers, and tic-tac-toe---can be represented abstractly by
\emph{game trees}.

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an~X.  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an~O, and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  The leaves
are labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating
the outcome for the first player.  (A win for one player is a loss for
the other---no ``everybody wins''-type games at MIT. \texttt{:-)})

A \emph{strategy} for a player in a game specifies which move the
player should make in any situation where it is that player's turn to
move.  A \emph{winning} stategy ensures that the player will win no
matter what moves the other player makes.  Similarly, a
\emph{non-losing} stategy ensures that the player will \emph{win or
  draw} no matter what moves the other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

More formally, let's define a family of Game Trees $T$ as follows:

1.  A single ``root'' node labeled with \emph{win}, \emph{lose}, or 
\emph{draw} is 
in $T$.

2.  An unlabelled root node connected to each element of a set of mutually 
disjoint
 game trees (not containing the root node either) called the ``immediate 
subgames''
 of the game tree is in $T$.


\ppart Prove that for any two-person game with a finite game
tree, at least one of the players has a non-losing strategy.

\solnospace{
\begin{proof}
The proof is by structural induction on the game tree.
Let $P(T)$ be the proposition that for a game tree, $T$, at least one
of the players has a non-losing strategy.

{\bf Base case:}
For the base case of a single-node tree, the node is labeled \emph{win},
\emph{lose}, or \emph{draw}.  If the node is labeled \emph{win} or
\emph{draw}, then the first player has a non-losing strategy.  If
the node is labeled \emph{draw} or \emph{lose}, then the second
player has a non-losing strategy.  In both cases, there is a player with
a non-losing strategy.

{\bf Structural Induction Step:} In the inductive step, we want to prove
that for any game tree, $T$, if $P(T')$ holds for each immediate
subgame, $T'$, of $T$, then $P(T)$ holds.

So suppose $T$ is a game tree and there is a non-losing strategy for at
least one of the players for every immediate subgame, $T'$, of $T$.

Let $A$ be the player who moves first in the game defined by $T$, and
let $B$ be the player who moves second.  If player $B$ has a non-losing
strategy for \emph{every} subgame, $T'$, of $T$, then $B$ also has a
non-losing strategy for the full game tree $T$: no matter what move
player $A$ makes, player $B$ simply follows his non-losing strategy for
the immediate subgame determined by $A$'s move.

On the other hand, suppose there is some immediate subgame, $T_0$, of
$T$, for which player $B$ does not have a non-losing strategy.  
Since, by induction hypothesis, \emph{some} player has a non-losing
strategy for $T_0$, it must be player $A$ that the non-losing strategy
for this subgame.  But then player $A$ has a non-losing strategy for the
full game tree $T$: namely, make the move that leads to subgame $T_0$
and then pursue the non-losing strategy for that subgame.

In either case, at least one of the players has a non-losing strategy.
This completes the proof of the induction step, and thus the whole proof
by structural induction.

We conclude that $P(T)$ holds for all games trees, $T$.
\end{proof}
}

\ppart Conclude that either one player has a winning strategy or both
players have non-losing strategies.

\solnospace{Call the players $C$ and $D$, and suppose neither one has a
winning strategy for the game, $T$.  We want to show that then \emph{both}
players have non-losing strategies for $T$.

The proof is based on the simple observation that in a game with no draws,
a non-losing strategy must be a winning strategy.  So in a game with no
draws, we conclude from part (a) that there is always a player with a
winning strategy.

\begin{proof}
To prove that $C$ has a non-losing strategy for the game, $T$, let's
consider another game, $T_C$, identical to $T$ except that draws are
considered wins for player $C$.  Since there are no draws in $T_C$, we
conclude that either $C$ or $D$ has a winning strategy for $T_C$.  But a
winning strategy for $D$ in the $T_C$ game would also be a winning
strategy for $D$ in the original game, $T$, because wins for $D$ are the
same in both games.  But we assumed that $D$ has no winning strategy for
$T$, so it doesn't have one for $T_C$.

That means that $C$ must have the winning strategy for $T_C$.  But a
winning strategy for $C$ in $T_C$ would also be a non-losing strategy for
$C$ in the original game, $T$, because wins for $C$ in $T_C$ are always
wins for $C$ or draws in $T$.  So we conclude that $C$ has a non-losing
strategy for $T$.

Notice that we haven't assumed that $C$ is the first or second
player, so the preceding argument applies equally well to show that $D$
also has a non-losing strategy for $T$, as required.
\end{proof}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%---------------------------------------------------------
% source: spring00 ps4
% topic: bipartite, tree, 2 coloring
% redone to add structral induction

\problem A 2-colorable graph is called {\em bipartite}.  Prove by
induction that every unordered unrooted tree is bipartite. The set of
{\em unordered unrooted} trees $T$ is defined recursively as follows:

1.  A single node is in $T$.

2.  If $t_1$ and $t_2$ are two disjoint trees in $T$, then the tree
    $t'$ formed by adding an edge from any vertex $v$ of $t_1$ to any
    vertex $u$ of $t_2$, is also in $T$.

\solnospace{
\begin{proof}
We want to prove that a tree is 2-colorable.  If we do this, then we
have shown that a tree is bipartite.  We will prove this using
structural induction.

{\bf Base case:} The base case is trivially true.  A single node can be
colored with just one color, meaning that it is two-colorable, and
therefor bipartite.

{\bf Structural Induction Step:}
Using rule 2 in the definition of an unordered,
unrooted tree, any tree is constructed out of two smaller trees, $t_1$
and $t_2$. Each of these trees, by our inductive hypothesis, is 
2-colorable.
Can we join $u$ from $t_1$ and $v$ from $t_2$ in a way such that our
new tree is also 2-colorable?  To do this, $u$ and $v$ must be
different colors.

Consider a 2-coloring of each of the smaller trees.  If vertex $v$
is a different color from $u$, then we can connect the
two trees to form the larger tree, and we are done.  If they are
different colors, then switch the coloring in $t_2$.  Now $u$ and $v$
are different colors, and can be connected.  Thus all possible trees
that can be constructed using the recursive definition must be 
2-colorable.
\end{proof}
}





%BEGIN Christos Fall 01

%-------------------------------------------------------------
% source  : spring00 ps3 
% topics  : critical path, DAGs, topological sort
% outcome : 4

\problem A pair of 6.042 students, Eleni and Paris,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of Paris' copy of the notes for tutorial 3.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
  paraphernalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Eleni's cat, Emilios - 11 days, after task \#1.
\item {\bf Open a Starbucks chain} for the army to get their caffeine - 10 
days, after task \#3
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3, \#4, and \#5.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#6.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#6.
\end{enumerate}

\problempart Express the information in the task list using some type
of graph (label the vertices to reflect task lengths).

\solution{%
    The information in the table is represented in the
    Figure~\ref{fig:tasks} in the form of a directed acyclic graph.
    Each vertex represents a task, and the weight of a vertex is the
    completion time.  Each directed edge represents a dependency
    between tasks.

    \begin{figure}[htbp]
    \begin{center}
    \unitlength=0.047pt
    \input{figures/ps4-1.latex}
    \end{center}
%      \centerline{\resizebox{!}{3.0in}{\includegraphics{figures/ps4-1.latex}}}
    \caption{Graph representing the task precedence constraints.}
    \label{fig:tasks}
    \end{figure}
}

\problempart Give some valid order in which the tasks might be
completed.

\solution{
We can easily find several of them. The most natural one is valid, too:
\#1, \#2, \#3, \#4, \#5, \#6, \#7, \#8.
}

\bigskip

Eleni and Paris want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.
\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Eleni cannot work on building a fleet for a few days, run get shots
for Emilios, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

\problempart Eleni and Paris want to know how long conquering the
galaxy will take.  Paris suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\solution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 11 + 10 + 4 + 6 + 8}{2} & = & 37 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Eleni and Paris from both working all the time.}

\problempart Eleni proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the most time-consuming sequence of tasks
such that each depends on the one before.  What lower bound does this
give, and why might it also be too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), opening a Starbucks (10 days), training
the army (4 days), and then defeating Microsoft (8 days).  Since these
tasks must be done sequentially, galactic conquest will require at
least 39 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Eleni and Paris may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Eleni and Paris
need to conquer the galaxy?  No proof is required.

\solution{
40 days.  Tasks could be divided as follows:

Paris: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days 33-40).

Eleni: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days 33-38).
}





%-----------------------------------------------------------------%
% source  : not sure, also has been used for many terms as a tutorial problem
% topic   : graphs, false proofs
% outcome : 2,3,4

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

\problempart
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}

\solnospace{
\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}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\problempart
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.

\solnospace{
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$.
}

\problempart
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.

\solnospace{
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{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}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\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}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not two-ended.}


\problempart
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$.''

\solnospace{
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.
}






%-----------------------------------------------------------------%
% source  : karger tutorial spring 01, 
%           used previous as pset, but was too hard apparently
% topic   : Dilworths theorem
% outcome : 1,4

\problem

In the lecture notes (section on scheduling) we proved

\begin{theorem}\label{antichain-partition}
If $t$ is the size of the longest chain in a poset $(A, \preceq)$
then $A$ can be partitioned into $t$ antichains.
\end{theorem}

Review: {\bf chain}: all elements comparable (total order); {\bf
antichain}: all elements incomparable.

We can use this 
%along with Pigeonholing 
to prove a famous result about posets:

\begin{theorem}
(Dilworth) If $t$ is the size of the longest chain in a poset with $n$
elements, then the poset has an antichain of size $\geq n/t$.
\end{theorem}

\begin{proof}
By Theorem~\ref{antichain-partition}, the $n$ elements can be
partitioned into $t$ antichains.
%The pigeons are the $n$ elements.  The holes are the $t$ antichains.
%By Strong Pigeonholing, 
All the $t$ antichains can't be smaller than $n/t$ or the total number of
elements would be less than $t(n/t) = n$, so some antichain must have at
least $n/t$ elements.
\end{proof}

Posets arise in all sorts of contexts, and when they do Dilworth's
theorem can have interesting implications.  As you will show in this
problem.

\textbf{Claim}:
In any sequence of $n$ different numbers, there is either an increasing
subsequence of length $> \sqrt{n}$ or a decreasing subsequence of length
$\geq \sqrt{n}$.

For example
\[ 6 4 7 9 1 2 5 3 8\]
has the decreasing sequence
\[6 4 1\]
and the increasing sequence
\[1 2 3 8.\]
That is, it has ``long'' subsequences of both kinds.

Consider some sequence of $n$ distinct numbers.  To prove the
claim, say for numbers $a,b$ in the sequence, that $a \preceq b$ iff 
both $a \leq b$ and $b$ doesn't come before $a$ in the sequence.

\bparts
\ppart  Verify that $a \preceq b$ is a partial order on the elements
of the sequence. 

\solnospace{
Let's use $a\textbf{ cb }b$ to denote that $a$ comes before $b$ in the
sequence. Then, $b$ doesn't come before $a$ iff $a\textbf{ cb }b\vee
a=b$. Let's denote this last fact as $a\textbf{ cb$_{=}$ }b$. It is
easy to check that \textbf{cb$_{=}$} is a total order. The same is
obviously true for $\leq$. The relation $\preceq$ is the intersection
of these orders. It's easy to verify that the intersection of two
partial orders is always a partial order, so $\preceq$ is a partial
order.  
}
%There are two total orders involved here: numerical $<$ and ``comes
%before'' in the sequence.  Let's abbreviate ``comes before'' as
%\textbf{ cb }.  The relation $\preceq$ is the intersection of these orders.
%It's easy to verify that the intersection of two partial orders is always
%a partial order, so $\preceq$ is a partial order.


\ppart What kind of subsequences are chains in this poset? \dots antichains?
Prove it.

\solnospace{
Increasing chains under $\preceq$ are the same as increasing subsequence,
because by definition, $a_1 \prec a_2 \prec \cdots \prec a_t$ iff both
\[a_1 < a_2 < \cdots < a_t,\]
and also
\[a_1 \mbox{\textbf{ cb }} a_2 \mbox{\textbf{ cb }} \cdots \mbox{\textbf{ cb }} a_t.\]

On the other hand, antichains are decreasing subsequences.  To prove this,
note:
\begin{lemma}\label{prec}
If $a,b$ are $\preceq$-incomparable and $a > b$, then $a
\mbox{\textbf{ cb }} b$.
\end{lemma}

\begin{proof}
If $b$ comes before $a$, then since $b < a$, we would also have $b \prec
a$, contradicting the assumption that $a$ and $b$ are incomparable.
\end{proof}

\begin{lemma}
If 
\[a_1 > a_2 > \dots > a_t,\]
and $a_1, a_2, \cdots, a_t$ are $\preceq$-incomparable,
then $a_1, a_2, \cdots a_t$ is a decreasing subsequence.
\end{lemma}

\begin{proof}
Since $a_i > a_{i+1}$, the next to last Lemma implies that $a_i$ comes
before $a_{i+1}$, that is, $a_1, a_2, \cdots a_t$ is a subsequence.
\end{proof}

So given an antichain, arrange the elements in decreasing order and this
will be a decreasing subsequence.
}

\ppart Prove the Claim.

\solnospace{
If there is no increasing subsequence of length $> \sqrt{n}$, then the
$\preceq$ partial order does not have a chain of length $> \sqrt{n}$.  By
Dilworth's Theorem, it must have an antichain of length at least
$n/\sqrt{n} = \sqrt{n}$.  But the elements of an antichain determine a
decreasing subsequence.}

\ppart Show that our 6.042 class of 100 students must contain either:

\begin{enumerate} 
\item 
a set $S$ of 10 students such that, if they line up in size
places, they are also arranged in increasing order of age, or

\item a set $T$ of 10 students such that, if they line up in size
places, they are also arranged in decreasing order of age.  
\end{enumerate}

\solnospace{Let $\preceq$ be ``is not younger than.''  The Claim implies
one or the other kind of sequence of length $\sqrt{100}$ will exist.}

%\emph{NOTE: Could change this to say that if we arranged the students
%alphabetically then it must contain either an increasing or decreasing
%height sequence of 10.}

\eparts



%-----------------------------------------------
% source: unknown, pRepository
% topics: adj matrices, chromatic number
% last used: ?
% outcome : 4

\problem The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
corresponds to row and column $i$ of the matrix.

\solnospace{ 
\begin{center}
\includegraphics[width=2in,height=2in]{figures/adjgraph}
\end{center}
%%\centerline{\resizebox{!}{2.0in}{\includegraphics{figures/adjgraph}}}
}

\problempart Give a coloring of the vertices that uses the minimum
number of colors. Prove that this a minimum coloring.

\solnospace{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}











%------------------------------------------------------------
% source: pRepository
% topic: general graphs
% outcome : 4

\problem Let $G$ be a graph.  Prove that there is a path from every
vertex of odd degree to some other vertex of odd degree in $G$.

\solnospace{
\begin{proof}
If graph $G$ has no vertex of odd degree, then the claim is true
vacuously.  Otherwise, let $v$ be a vertex of odd degree.  Consider a
longest path starting at $v$ in which each edge occurs at most once.
Then every edge leaving the final vertex on the path must already be
on the path.  We will show that this final vertex of the path is
another vertex of odd degree.

Since $v$ has odd degree, the path contains at least one edge.
Furthermore, the final vertex of the path cannot be $v$, since the
edges incident to $v$ would then consist of the first and last edge of
the path plus two edges for each time that the path crosses $v$--- an
even total.  Therefore, the edges incident to the final vertex of the
path consist of the final edge of the path plus two edges for each
time that the path crosses the final vertex--- an odd total, as
claimed.
\end{proof}
}


%-----------------------------------------------
% source: Rosen 7.8.21 (rewritten to be more clear, 
%	  STILL CONFUSING! ---see side note at the end)
% topics: coloring application (register coloring)
% last used: first time
% outcome : 4

\problem My computer program has seven variables, {\tt t,u,v,w,x,y,z},
and computes in 6 steps. The steps in which each variable is used are
as follows: {\tt t:} steps 1 through 6; {\tt u:} step 2; {\tt v:}
steps 2 through 4; {\tt w:} steps 1,3 and 5; {\tt x:} steps 1 and 6;
{\tt y:} steps 3 through 6; {\tt z:} steps 4 and 5. Each variable will
need to occupy the same index register at each one of the steps in
which it is going to be used; however during the steps when the
variable is not being used the register may be used by some other
variable. How many such registers are needed for my program? Explain
how you arrived at the answer.

\solnospace{This problem shows an application of graph coloring to
register allocation in a processor. Consider a simple graph $G$ having
the seven variables as its nodes, and an edge between two variables
iff there is at least one step of the program during which both
variables are going to be used.  Figure~\ref{fig:vars} contains the
graph we are talking about.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{figures/ps4-4a.latex}
\end{center}
\caption{}
\label{fig:vars}
\end{figure}

Clearly, two variables have to occupy different index registers iff
they are going to be used simultaneously sometime during the
progam execution, that is, iff they are connected in~$G$. 

To correctly and economically assign variables to registers means to
map each variable to one register in a way that does not cause
collisions (two simultaneously used variables mapped to the same
register) and uses as few registers as possible. But (if we think of
registers as colors) this is the same as to color $G$ in a way that
does not cause neighboring vertices of the same color and uses as few
colors as possible. So, we have reduced the original problem to the
problem of coloring~$G$.

Figure~\ref{fig:varscol} shows such a coloring, using 5 colors. To see
that this is the minimum one, just notice that variables $t$, $v$,
$w$, $y$, and $z$ form a 5-vertex subgraph which is complete, and
hence cannot be colored with less than~5 colors.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{figures/ps4-4b.latex}
\end{center}
\caption{}
\label{fig:varscol}
\end{figure}

SIDE NOTE: In this problem we have assumed that a variable must always
use the same register, i.e. a variable is assigned a single
color. However in a real compiler this is overly restrictive because a
variable is backed up into memory every time it is evicted from the
register set and then reloaded from memory into the register set when
it needs to be used again. When it is reloaded there is no reason why
the same register must be used. For example, say we had a variable $x$
which is used in steps 1,2,3 and then later used in step 6. Then $x$
could be stored in register $r1$ for steps 1 through 3 and some other
register $r2$ for step 6. We can still use coloring to solve the
problem by treating $x$ as two separate variables: $x_{123}$ and
$x_6$. Since the number of variables in a computer program can be very
large and the register set of a processor is typically much smaller
(16-64 registers), register allocation is an important piece of
compiling.

}


%-----------------------------------------------
% source: Spring 95 Quiz 1, pRepository
% topics: graph connectivity
% outcome : 4

\problem The {\em complement} of an undirected graph $G=(V,E)$ is the
graph $\bar{G}=(V, \bar{E})$.  That is, $\bar{G}$ contains exactly
those edges that are not in $G$.  Prove that if $G$ is not connected
then $\bar{G}$ is.

\solnospace{
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $\bar{G}$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $\bar{E}$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $\bar{G}$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $\bar{G}$ is connected.
}






%-----------------------------------------------
% source: used by Albert in Fall 99, occasional tutorial
% topics: relations, adj matrices, paths, graphs
% outcome : 1,3,4

\problem Let $A$ be the adjacency matrix for a digraph $G$ with $n$
vertices.  Note that $A$ is a zero-one valued $n \times n$ matrix.  In
this problem we use the Boolean ``OR'' operation, $\vee$, instead of
``+'' when multiplying zero-one valued matrices (this is called
``boolean'' matrix product).

\problempart

For $k \geq 1$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

  \solnospace{%
    We prove this by induction on $k$.
%    Let $P(n)$ be the predicate that ${A^n}_{ij} = 1$ iff there is a
%    directed path of length $n$ from the $i$th to the $j$th vertex
%    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
%    on $n$.

    {\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix
    A, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$. We know,
    \[
	{A^{k+1}}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})
    \]

Now we consider both directions for the iff.


[$\Leftarrow$]
Suppose there is a directed path of length $k+1$ from the $i$th to the
$j$th vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  ${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,
\[
({A^k}_{il} \wedge A_{lj}) = 1
\]
which implies
\[
{A^{k+1}}_{ij} = 1.
\]

[$\Rightarrow$] 
Suppose that ${A^{k+1}}_{ij} = 1$. 
Then $\exists\; l \in V_G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}


\problempart Let $B = A \vee I$ where $I$ is the $n \times n$ identity
matrix.  Prove that ${B^k}_{ij} = 1$ iff there is a directed path of
length $\leq k$ from the $i$th to the $j$th vertex of $G$.

  \solnospace{%
    From part~(a), it can be seen that ${B^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since ${B^k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    ${B^k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.%
    }%
  

\problempart Conclude that ${B^n}_{ij} = 1$ iff there is a directed
path from the $i$th to the $j$th vertex.

\solnospace{
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$\leq n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $\leq n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $\leq n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}

\problempart If $A$ is the matrix for a relation $R$, show that $B^n$
is equal to the reflexive and transitive closure of $R$.

\solnospace{It is easy to see that the reflexive and transitive
closure of $R$ is $R^*\cup\Delta$, where $R^*$ is the connectivity
relation for $R$ (Rosen, p.~399--400), and $\Delta$ is the diagonal
relation on the set of vertices.

Now, to show that $B^n$ is the matrix of $R^*\cup\Delta$, it suffices
to show that 
$$
\text{for every two vertices $i$, $j$:} \quad
B^n_{ij} = 1 \iff (i,j)\in R^*\cup\Delta.
$$
The case where $i=j$ is easy: By definition of $\Delta$,
$(i,i)\in\Delta$, hence $(i,i)\in R^*\cup\Delta$; and, since there
exists a path (of length~0) from $i$ to $i$, $B^n_{ii}=1$,
by~(c). Therefore, the equivalence holds. 

For the case where $i\neq j$: If $B^n_{ij}=1$, then, by~(c), there is
a path from $i$ to $j$, which is of length at least~1 (because $i\neq
j$). Hence $(i,j)\in R^*$, so $(i,j)\in R^*\cup\Delta$,
too. Conversely, suppose $(i,j)\in R^*\cup\Delta$. Then, since $i\neq
j$, it has to be the case that $(i,j)\in R^*$, hence there exists a
path from $i$ to $j$. Which, by~(c), implies that $B^n_{ij}=1$.

Therefore, the equivalence holds in all cases, which implies $B^n$ is
indeed the matrix of $R^*\cup\Delta$.
}









%-----------------------------------------------
% source   : Rosen ??
% topics   : isomorphism
% outcomes : 4

\problem A graph $G$ is {\em self-complementary} if $G$ and $\bar{G}$ are
isomorphic. $\bar{G}$ is the complement of $G$ as defined in problem 6.

% The symbol $\bar{G}$, where $G$ is a graph, is defined in problem 33
% on page 456 of Rosen. The term ``isomorphic'' is defined on page 460
% of Rosen.

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solnospace{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\begin{center}
\includegraphics[width=1.5in]{figures/selfcomp}
%%\centerline{\resizebox{!}{1.5in}{\includegraphics{figures/selfcomp.eps}}}
\end{center}

}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solnospace{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is congruent to either 0 or 1 mod 4 (hint:
use part (b)).

\solnospace{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}



%END Christos Fall 01




\end{problems}

\end{document}


