\documentstyle[12pt,twoside,amstex,amsfonts,psfig]{article}

\raggedbottom

\input{macros-course}

\newtheorem{falsethm}[theorem]{False Theorem}

\begin{document}

\tutn{3}{2/19/99}{February 19, 1998}

\section{Buildup Error}

``Buildup error'' is a common source of mistakes in inductive proofs.
We saw an example in lecture; here's another:

\begin{quotation}
\noindent {\bf False Theorem}: If every vertex in a vertex-colored simple
graph is adjacent to a vertex of the same color, then the graph is
monochromatic.
\end{quotation}

{\bf Class exercise}.  Exhibit a simple counter-example to this claim.

{\bf Solution}: A cycle on four vertices with two red vertices followed by
two blue vertices.  Each vertex is adjacent to some vertex of the same
color, but the graph is not monochromatic.

{\bf False Proof}: By induction on the number of vertices in the
graph.  Let $P(n)$ be the predicate, ``If every vertex in an $n$-vertex
vertex-colored simple graph is adjacent to a vertex of the same color,
then the graph is monochromatic.''

In the base case, $P(1)$, the graph contains only one vertex and so is
certainly monochromatic.

For the inductive step, we assume $P(n)$ in order to prove $P(n+1)$.  For
$n\geq 1$, let $G=(V,E)$ be a vertex-colored graph with $n+1$ vertices
such that every vertex is adjacent to a vertex of the same color, and let
$v \in V$ be an arbitrary vertex.  Let $G'$ be the subgraph of $G$
obtained by deleting $v$.  Since $G'$ is an $n$-vertex graph, we have by
induction that $G'$ is monochromatic.  By hypothesis, $v$ is adjacent to a
vertex $v'$ of the same color.  Since $v'$ must be a vertex of $G'$, it
follows that $v$ has the same color as all the other vertices.  Therefore,
$G$ is indeed monochromatic. \qed


{\bf Class Exercise}.  Pinpoint the flaw in this proof.

{\bf Solution}: the flaw is in the statement, ``Since $G'$ is an
$n$-vertex graph, we have by induction that $G'$ is monochromatic.''  This
is incorrect.  We can assume only that {\bf if} {\em every vertex in $G'$
is adjacent to a vertex of the same color}, {\bf then} we have by
induction that $G'$ is monochromatic.''  Unfortunately, removing $v$ from
$G$ may yield a $G'$ for which the adjacency condition fails.

\medskip
The correct assumption does not apply to $G'$ and does not lead to a
proof.  Of course a breakdown of the proof was inevitable, since the
theorem is false!

{\bf Class exercise}: Verify that the red/blue 4-cycle above is example
where the adjacency assumption fails for $G'$.

{\bf Solution}: We saw red/red/blue/blue 4-cycle satisfies the adjacency
condition.  Now remove, say, a red vertex.  Resulting graph red/blue/blue
graph leaves red vertex w/o a red neighbor.


\section{Bipartite Graphs}

Recall that a graph is $k$-colorable if every vertex can be assigned
one of the $k$ colors so that no adjacent vertices have the same
color.  A 2-colorable graph is called {\em bipartite}.  Many common
types of graph are bipartite, and they often arise in computer
science.

\begin{theorem}
Every tree is bipartite.
\end{theorem}

Before proving this theorem, we'll first prove a lemma about trees.

\begin{lemma}
Every tree with more than one vertex has a vertex of degree one.
\end{lemma}

\begin{proof}
The proof is by contradiction.  Suppose that there is an
$n$-vertex tree that has no vertex of degree one.  Since the tree is
connected and has more than one vertex, no vertex can have degree zero.
As a result, every vertex must have degree at least two.  Since the number
of edges in a graph is half the sum of the degrees, the number of edges
must be at least $\frac{1}{2} (2n) = n$.  This contradicts the fact that
an $n$-vertex tree has exactly $n-1$ edges.
\end{proof}

Now we can use the lemma to prove the theorem that every tree is
bipartite.

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate
that every tree with $n$ vertices is bipartite.  In the base case,
$P(1)$ is true because a graph consisting of a single vertex can be
colored with just one color.  In the inductive step, for $n \geq 1$
assume that every tree with $n$ vertices is bipartite in order to
prove that every tree with $n+1$ vertices is bipartite.

Let $G$ be a tree with $n+1$ vertices.  By the lemma, we can pull off
a vertex $v$ with degree one.  The remaining $n$-node graph is a tree.
(The reason is that we removed one node and one edge and did not
introduce a cycle.  Therefore, the remaining graph is acyclic and has
$n$ nodes and $n-1$ edges.  This defines a tree.)  By induction, the
remaining graph is bipartite.  The extra vertex $v$ can take whatever
color that its single neighbor does not.
\end{proof}


\section{Counting Graphs}

How many simple
graphs (up to isomorphism) are there with $|V| = |E| = 5$?
\medskip

{\bf Solution:} Since $|V| = |E| > |E| - 1$, any such graphs must have a
cycle.  If two graphs are isomorphic, then they must have the same size
maximum cycle.  (This should be clear).  So we can classify graphs by size
of maximum cycle.

If the maximum cycle is five, there is only one graph, and the entire
graph is that cycle.  If the maximum cycle is four, there are two graphs,
one with one connected component, and one with two connected components.
If the maximum cycle is three, there is one disconnected graph and two
connected graphs, depending on how the two vertices not in the cycle are
(or are not) connected to the 3-cycle.  Since by definition a cycle must
be of size at least three, we are done.

\section{Posets}

The connectedness relation of a DAG is a {\em partial order}.  These come
up in Computer Science all the time.  The Course Scheduling example from
lecture was one illustration of the application of partial order concepts.

Remember that in a digraph, vertex $u$ is said to be {\em connected} to
vertex $v$ iff $u=v$ or there is a path from $u$ to $v$.  If we write $u
\succeq v$ to mean that $u$ is connected to $v$, then $\succeq$ is a
binary relation on the vertices which is obviously \emph{transitive}:
\[ [u \succeq v \wedge v \succeq w] \implies u \succeq w,\]
and, because the digraph has no cycles, it is \emph{antisymetric}:
\[ [u \succeq v \wedge v \succeq u] \implies u = v.\]
Formally, a partial order on a set is just a binary relation which is
transitive and antisymetric\footnote{Rosen also requires that a partial
order be \emph{reflexive}: $v \succeq v$ for all $v$.  In 6.042 we will
not always insist on reflexivity.  For example, we will consider the
relation $v \succ u$ --- defined to mean that there is a directed path
(which by definition is of \emph{positive} length) from vertex $u$ to $v$
--- to be a nonreflexive partial order on the vertices of a DAG.  Note
that the connectedness relation, $\succeq$, of a DAG is in fact reflexive
by our definition, because we explicitly specify that every vertex is
connected to itself.}.

The \emph{coordinatewise} $\geq$ relation on $n$-bit vectors $a,b$ is a simple
example of a partial order: define $a \succeq b$ iff $a_i \geq b_i$ for $1
\leq i \leq n$.  Here's a DAG with $V = \set{0,1}^3$ whose connectedness
relation is exactly the same as $\succeq$:

DRAW THE CUBE WITH DIRECTED EDGES DOWN.

Two elements $u$ and $v$ are said to be {\em comparable} under a partial
order, $\succeq$, iff either $u \succeq v$ or $v \succeq u$; otherwise,
$u$ and $v$ are \emph{incomparable}.  For example, $100$ and $010$ are
incomparable elements in the cube above.

The most familiar example of a partial order is the order $<$ on real
numbers.  This partial order is a special one because it is actually a
\emph{total} order.  The \emph{totality property} says that every two
elements are comparable:
\[\forall u \neq v : u < v \vee v < u.\]

Notice that if $\succeq$ is a partial order, so is $\preceq$ defined by
the rule that $u \preceq v$ iff $v \succeq u$.  Sometimes we don't want to
prejudice whether we're thinking of a partial order as ``bigger than'' or
``smaller than,'' so we choose some symbol like $R$ for the relation and
write $uRv$ instead of $u \succeq v$.

Technically, a partial order is always defined on some set $P$.  The set
together with the partial order is called a \emph{partially ordered set} or
\emph{poset}.

Examples:

\begin{enumerate}
\item $(\naturals, |)$ is a poset.  That is, the ``divides'' relation $|$
is a partial order on the set of natural numbers.  It is not total (WHY?
-- because, eg, neither $3|5$ nor $5|3$.)  Note that if we talk about
divides as a ``smaller-than'' relation, then zero is a \emph{maximum}
element, namely smaller than every other element, and one is a
\emph{minimum} element.

\item QUESTION: why isn't $(\integers, |)$, a poset?

\item $(P(\naturals), \subseteq)$ is a poset.  That is, the containment
relation is a partial order on the subsets of natural numbers.  It is not
total (WHY? -- because, eg, neither $\{3\}\subseteq \{5\}$ nor $\{5\}
\subseteq \{3\}$)

\item Dictionary order on words over the English alphabet is a total
order.
\end{enumerate}

\section{Team Problems}
\begin{problems}

\problem Define a DAG to be \emph{connection-minimal} iff no edge can be
deleted from it without changing the connectedness partial order on the
vertices of the DAG.

\bparts

\ppart  Describe a connection-minimal four-vertex DAG with as few edges as
possible.

\emph{Solution} no edges.

\ppart Describe all the connection-minimal DAG's with three vertices.

\emph{Solution}: vertical line of three, V, and Wedge, all directed down,
are the only connected cases.  There's one case with exactly 2 connected,
and one case w/none connected.

\ppart Prove that for any DAG, $G=(V,E)$, there is a \emph{unique}
connection-minimal DAG $M=(V,E')$ on the same set of vertices as $G$ such
that $G$ and $M$ define the same connectedness partial order.

\emph{Solution}: Define an edge $(u,v)$ to be \emph{necessary} iff it is
the \emph{only} path from $u$ to $v$.  Let $N$ be the set of necessary edges.

Prove that if $(V,E_0)$ defines the same connectedness relation on a DAG
as $G$, then $N \subseteq E_0$.  Then prove that $(V, N)$ defines the same
connectedness relation as $G$. So $E' = N$.

\eparts

\problem The weighted graph in Figure~\ref{fig:flowprob} 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 \emph{capacity} of the system, that is, the maximum rate at
which water can pass through the entire system in gallons per second.

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

\bparts

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

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

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

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

If you've done it right, your lower bound on the capacity of the system
from part (a) will equal your upper bound from part (b).

\emph{Solution}: The edges marked with X's in Figure~\ref{fig:flowsol} have
a total capacity of 7 gallons per second.  Removing these edges
disconnects $S$ from $T$.  Therefore, the capacity of the system is at
most 7 gallons per second.


\eparts

\problem We proved in lecture that if every edge in $K_6$, the complete
graph with six vertices, is colored solid or dashed, then there must be a
solid triangle or a dashed triangle connecting three of the vertices.  If
we delete the dashed lines, then we could rephrase this observation from
lecture by saying that given any simple graph with six vertices, either it
contains a copy of $K_3$ or there are three vertices with no connections
between them.

The observation from lecture illustrates a very general theorem about
simple graphs due to Ramsey.  A subset, $A$, of the vertices of a simple
graph such that no two vertices in $A$ have an edge between them, is
called an {\em anti-clique} of the graph.  Ramsey's Theorem implies that
for any $n>0$, every ``large enough'' simple graph contains a copy of
$K_n$ \emph{or} has an anti-clique of size $n$.  This will follow from
\begin{lemma}
Let $m$ and $l$ be positive integers, and $G$ be a simple graph.  If $G$
has $\geq m^{l}$ vertices, then either $G$ contains a copy of $K_l$ or $G$
contains an anti-clique of size $m$.
\end{lemma}

\bparts

\ppart Use the Lemma to determine how big ``large enough'' is.

\emph{Solution}: $n^n$ vertices.

\ppart Let $G$ be a simple graph with $n>0$ vertices.  Prove that if $G$
has no vertex of degree $\geq m$, then $G$ has an anti-clique of size
$\geq n/m$.

\medskip
{\em Solution}: By strong induction on the number of vertices of $G$.

The base case $n \leq m$ follows by choosing the anti-clique to consist of
a single vertex.

So for the induction case, suppose $n > m$.  Pick any vertex of, $v$, of
$G$.  Remove $v$ and all vertices adjacent to $v$ from $G$; call the
remaining graph, $H$.  Now $H$ has at least $n - m$ vertices because $v$
has degree $< m$, and by definition of $H$, none of the vertices in $H$
are adjacent (in $G$) to $v$.  Since removing vertices does not increase
degrees, $H$ also has no vertex of degree $\geq m$.  By strong induction,
there is an anti-clique $A$ of $H$ of size at least $(n-m)/m = n/m - 1$.
So $A \cup \{v\}$ is an anti-clique of $G$ of size at least $n/m$. \qed

\ppart Prove the Lemma.

\hint Induction on $l$.  There are two cases, (1) when every vertex of $G$
has degree $< m^l$, or (2) when some vertex does have degree $\geq m^l$.
The previous problem part handles case (1).

\begin{proof}

The base case $l=1$ follows because $m^1 \geq 1$, and every graph with at
least one vertex has $K_1$ as a subgraph.

So assume that $G$ has at least $m^{l+1}$ vertices.  There are two cases:

(1) Every vertex of $G$ has degree $< m^l$.  Then by the previous problem
part, $G$ has an anti-clique of size at least $m^{l+1}/m^l = m$.

(2) Some vertex, $v$, of $G$ has degree $> m^l$.  Let $H$ be the subgraph
obtained by restricting $G$ to the vertices adjacent to (and not
including) $v$.  Now $H$ has $\geq m^l$ vertices, so by induction, either
$H$ contains $K_l$ or has an anti-clique of size $l$.

Now an anti-clique of $H$ will also be an anti-clique in $G$, so if $H$
contains an anti-clique of size $m$, so does $G$, and the
Theorem holds.  Otherwise, $H$ contains a subgraph, $C$, which is a copy
of $K_l$.  So $C \cup \{v\}$ is the required copy of $K_{l+1}$ in
$G$.

\end{proof}

\eparts

\end{problems}

\end{document}





