\documentclass[11pt,twoside,xypic]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}


\newcommand{\solution}[1]{}
\newcommand{\depth}{\mbox{depth}}
\newcommand{\height}{\mbox{height}}
\newcommand{\lcm}{\mbox{lcm}}

\begin{document}

\tutprobn{8}{10/8/99}{October 8, 1999}

\begin{problems}

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

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

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

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

Obviously, $G_n$ is not a line graph.
}

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

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

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

\solution {

no edges.}

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

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

\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
In the handout on Graphs and Trees (H23, p. 18, example on course
schedualing) we  proved  that 
\begin{theorem}
If $t$ is the length 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 length 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 previous result, the $n$ elements can be partitioned into
$t$ antichains.  The pigeons are the $n$ elements.  The holes are the $t$
antichains.  By Strong Pigeonholing, there must be $\geq n/t$
pigeons in some hole.
\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$ numbers.  To prove the claim, say for
numbers $a,b$ in the sequence, that $a \preceq b$ iff either $a = b$, or
else both $a < b$ and also $a$ comes before $b$ in the sequence.

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

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

\ppart Prove the Claim.
\eparts

\solution{
\medskip

(a) 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.

(b) 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 > \cdots 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}$, Lemma~\ref{prec} 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.

(c) 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.}


\end{problems}

\end{document}

