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

\raggedbottom

\input{macros-course}

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

\begin{document}

\tutprobn{3}{2/19/99}{February 16, 1998}

\textbf{Class exercise}:

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

Pinpoint the flaw in this proof.

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

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

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

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

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

\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} 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 has
an anti-clique of size $m$.
\end{lemma}

\bparts

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

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

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

\end{problems}

\end{document}
