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

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

\bparts

\ppart

For $k \in \naturals$, 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 vertices of $G$.

\solution{

{\bf Proof:} by induction on k.\\

{\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 vertices 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 vertices of $G$.\\

{\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$.\\
\[{A^k}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})\]\\
Now we consider both directions for the iff.\\
Case 1: There is a directed path of length $k+1$ from the $i$th to the $j$th vertices 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\]
\[{A^k}_{ij} = 1\]

Case 2: ${A^{k+1}}_{ij} = 1$.\\
Then $\exists l \in 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.\\}

\ppart

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 vertices of $G$.

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

\ppart 

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

\solution{
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
$<=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 $<=n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $<=n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\}

\eparts



















\problem
{ \em
Prove that for any relations $Q,R$ and $S$
\[ Q\circ (R^c \circ S)^c \subseteq ((Q\circ R)^c\circ S)^c. \] }

\iffalse 
Given any pair, $(a,d) \in Q \circ (R^c \circ S)^c $, there must exist
some $c$ such that $(a,c) \in (R^c \circ S)^c $ and $(c,d) \in Q$.
Now since $(a,c) \in (R^c \circ S)^c$, $(a,c) \notin (R^c \circ S)$
and there exists {\em no} $b$ such that $(a,b) \in S$ and $(b,c) \in R^c$.
This means that for every $b$, $(a,b) \in S^c$ and $(b,c) \in R$.

Now given all of this, show that $(a,d)$ is a member of $((Q\circ R)^c\circ S)^c$:

Since there exists a $c$,$d$ such that $(c,d) \in Q$ 
and for every $b$, $(b,c) \in R$, then for every $b$, $(b,d) \in
Q \circ R$ and there is no $b$ such that $(b,d) = (Q \circ R)^c$.
But recall that  there is also no $b$ such that 
$(a,b) \in S$, so $(a,d) \notin ((Q\circ R)^c \circ S) $
and $(a,d) \in ((Q\circ R)^c \circ S)^c $
and the statement is proved.
\fi

We want to prove that for any $(a,d)$, if 
$(a,d)\in Q\circ (R^c\circ S)^c$ then 
$(a,d)\in ((Q\circ R)^c\circ S)^c$.
Assume for contradiction this is not true, 
i.e., for some $(a,d)$ we have
$(a,d)\in Q\circ (R^c\circ S)^c$ and
$(a,d)\in ((Q\circ R)^c\circ S)$.
From the definition of composition we know there exist
$b$ and $c$ such that 
$(a,b)\in (R^c\circ S)^c$, $(b,d)\in Q$,
$(a,c)\in S$ and  $(c,d)\in (Q\circ R)^c$.

We claim that $(c,b)\in R$. The proof is again 
for contradiction: assume $(c,b)\in R$ is false.
We have $(c,b)\in R^c$ and we know that $(a,c)\in S$.
From the definition of composition we get 
$(a,b)\in R^c\circ S$, which contradicts 
$(a,b)\in (R^c\circ S)^c$.

So, $(c,b)\in R$ and since we know that 
$(b,d)\in Q$, we also have $(c,d)\in Q\circ R$.
This is a contradiction because 
$(c,d)\in (Q\circ R)^c$.
\problem 
A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\bparts

\ppart Every symmetric, weakly transitive relation is transitive.

\solution

The claim is false.  The diagram below shows a counterexample.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
\end{figure}


\ppart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution

\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}


\eparts

\problem

{\em
Show that the transitive closure of the symmetric closure of the
reflexive closure of a relation $R$ is the smallest equivalence
relation that contains $R$.
}

Let $A$ be the set that $R$ is a relation on.  Let $S$ be the
transitive closure of the symmetric closure of the reflexive closure
of a relation $R$.  We need to prove that $S$ is an equivalence
relation, and then we need to prove that any equivalence relation that
contains $R$ also contains $S$ and is therefore bigger than $S$.

To prove $S$ is an equivalence relation, we need to prove it is
reflexive, symmetric, and transitive.  

Reflexivity is easy.  Note
that we got $S$ by performing 3 ``closure'' operations on $R$, each of
which adds (but does not remove) some pairs to the relation.  The
first, reflexive closure added all pairs $(a,a)$ for $a \in A$, and
neither of the symmetric or transitive closure operations remove these
pairs.  So $S$ has them all, and is reflexive.  

Now let $T$ be the symmetric closure of the reflexive closure.
Clearly $T$ is reflexive and symmetric, and $S$ is the transitive
closure of $T$.  We use this to prove $S$ is symmetric.  Suppose
$(a,b) \in S$.  Then by the definition of transitive closure of $T$,
there's a path $(a=x_0,x_1,x_2,\ldots,x_n,b=x_{n+1})$ such that each
$(x_i,x_{i+1}) \in T$.  It follows from the symmetry of $T$ that each
$(x_{i+1},x_i) \in T$, which implies (since $S$ is a transitive
closure) that $(x_{n+1},x_0)=(b,a) \in S$.  So $S$ is symmetric.

Transitivity is also easy---since $S$ is a transitive closure, it is
transitive. 

Now we have to prove that any equivalence relation containing $R$ also
contains $S$.  Suppose we have an equivalence relation $P \supseteq
R$.  It follows that the reflexive closure of $P$ contains the
reflexive closure of $R$.  but since $P$ is reflexive, its reflexive
closure is $P$---that is, $P$ contains the reflexive closure of $R$.
It follows that the symmetric closure of $P$ contains the symmetric
closure of the reflexive closure of $R$, namely $T$.  But again, since
$P$ is an equivalence relation, its symmetric closure is $P$, meaning
$P \supseteq T$.  For similar reasons, $P \supseteq S$, as claimed.


\problem 
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{ps3-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{ps3-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{ps3-noauto.eps}}}
\end{figure}

\end{problemparts}


%\problem 
%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{ps3-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

For each pair of graphs determine whether they are isomorphic. If so,
exhibit the isomorphism; if not, prove they are not.
\bparts
\ppart
\[
\diagram
 & \b \dlline\drrline\xline'[1,0][2,0] & & \\
 \b \xline'[0,3]\ddline & & & \b\ddline\\
 & \b \dlline\drrline & & \\
 \b \xline'[0,3] & & & \b\\
\enddiagram
\quad\quad
\diagram
 & \b \dlline\drrline\xline'[1,0][2,0] & & \\
 \b \xline'[0,3]\xline'[2,3] & & & \b\xline'[2,-3]\\
 & \b \dlline\drrline & & \\
 \b \xline'[0,3] & & & \b\\
\enddiagram
\]

\ppart
\[
\diagram
 & \b \rrline\xline'[1,0][2,0] & & \b \ddline\\
 \b \urline\rrline\ddline & & \b \urline\ddline\\
 & \b \xline'[0,1][0,2] & & \b\\
 \b \rrline\urline & & \b \urline
\enddiagram
\quad\quad
\diagram
 & \b \rrline\xline'[1,0][2,0] & & \b \xline'[3,-1]\\
 \b \urline\rrline\ddline & & \b \urline\drline\\
 & \b \rrline & & \b\\
 \b \rrline\urline & & \b \urline
\enddiagram
\]

\ppart
\[
\spreaddiagramrows{-1pc}
\spreaddiagramcolumns{-1pc}
\diagram
 &  &  &  \b \xline'[2,-3]\dline\xline'[2,3]&  &  &  &   \\
 &  &  &  \b \xline'[3,-1]\xline'[3,1]&  &  &  &   \\
 \b \xline'[0,1]\xline'[3,1]&\b \xline'[0,4]\xline'[2,3]  &  &  &  & \b \xline'[2,-3]   &  \b \xline'[0,-1]\xline'[3,-1] \\
 &  &  &  &  &  &   \\
 &  &  \b \xline'[1,-1]&  &  \b \xline'[1,1]&  &   \\
 &  \b \xline'[0,4]&  &  &  &  \b &
\enddiagram
\quad\quad
\diagram
 & & \b \dllline\dline\drrline& &\\
 \b \xline'[4,0]\xline'[3,3] & & \b \dline\xline'[1,0];[2,1]*(0.5,0)'[5,0] & & \b \xline'[4,0]\xline'[3,-3]\\
 & & \b \ddlline\ddrline & & \\
 & & & & \\
 & \b \dlline& & \b \drline & \\
 \b \drrline& & & & \b \dllline\\
 & & \b & &
\enddiagram
\]

\ppart {[EXTRA:]} Consider the two copies of the complete graph, $K_3$, with 3
vertices labeled 1,2 and 3.  Let $\sigma$ be a permutation on the set
$\{1,2,3\}$. Join the two graphs by placing an edge between vertex $i$
of the first graph and vertex $\sigma(i)$ of the second graph. For
example, the first graph in part a) was obtained using the identity
permutation, and the second one was obtained using the permutation
that sends 1 to 2, 2 to 1 and 3 to 3.  Given any two permutations
$\sigma_1$ and $\sigma_2$, are the two graphs isomorphic?

\eparts

\problem 
{\em
Define a relation $R$ on $\naturals$ by, $(a,b) \in R$ if 
$\exists c \in \naturals$ such that $a^2 = b^2 + c^2$.

Decide whether $R$ is reflexive, symmetric, antisymmetric, or transitive.
}

\solution 

Reflexive: \\
$a^2 = a^2 + c^2$ is true when $c=0$.  So $R$ is reflexive.

Symmetric: \\
$a^2 = b^2 + c_1^2 \leftrightarrow b^2 = a^2 + c_2^2$?
No.  Let $a=5, b=4, c_1=3$ but $4^2 = 5^2 + c_2^2$ has no solution in the
natural (or even real) numbers.


Antisymmetric: \\
Yes.  Show that  $(a,b) \in R \wedge (b,a) \in R \rightarrow a = b$.
$a^2 = b^2 + c_1^2$ rearranges to 
$b^2 = a^2 - c_1^2 = a^2 + c_2^2$.  However, we cannot find any solution to 
$c_2^2 = -c_1^2$, unless $c_1 = c_2 = 0$, in which case $a=b$ .  Since there is no solution for $c_2 \in \naturals$,
R is antisymmetric.

Transitive: \\
$(x,y) \in R \wedge (y,z) \in R \rightarrow (x,z) \in R$?  No.  Case against:\\
$(13,5) \in R \rightarrow 169 = 25+ 144$ and 
$(5,4) \in R \rightarrow 25=16+ 9$, but $(13,4) \notin  R$ since $13^2 = 16+c^2$,
so $c^2=153$ and $153$ is not a square, so there's no solution for $c$.
R is not transitive.



\eparts
\problem 
For an integer $k\geq 1$, let $\naturals^k$ be
the set of $k$-tuples of natural numbers.  So every $x\in
\naturals^k$ is a $k$-tuple of the form $(x_1, x_2, \ldots, x_k)$ where
each $x_i\in\naturals$.

Define a binary relation, $\leq_k$, on $\naturals^k$ by the condition:
\[
x \leq_k y \mbox{ iff } x_i \leq y_i \mbox{ for all } i, 1\leq i \leq k.
\]
The relation $\leq_k$ is a partial order on $\naturals^{k}$.  It is called
the {\em coordinatewise}, or {\em pointwise} partial order on $k$-tuples.

\begin{enumerate}
\item Describe a set of 103 elements of $\naturals^{2}$ which are pairwise
incomparable.  That is, for any two distinct pairs $x,y$ among your 103,
neither $x \leq_2 y$ nor $y \leq_2 x$.  (Such a set of incomparable
elements of a poset is called an {\em antichain}.)

\item Let $X = x^{1},x^{2},\ldots$ be an infinite sequence of $k$-tuples
in $\naturals^{k}$.  Prove that $X$ has an infinite non-decreasing
subsequence, that is, there is an infinite increasing sequence of integers
$0 < i_{1} < i_{2} < \ldots$ such that
\[
x^{i_{1}} \leq_{k} x^{i_{2}} \leq_{k} \ldots.
\]

\item Conclude that there is no infinite antichain in $\naturals^{k}$ for
any $k\geq 1$.
\end{enumerate}

