\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.1in}

\begin{document}
\pset{8}{April 3, 1997}{April 10, 1997}

{\bf Reading:} Rosen 7.1-7.4 (skip isomorphism), 7.8, 8.1

\begin{problems}
\problem 
Answer the following questions concerning the poset consisting of the elements
\{\{a\},\{b\},\{d\},\{a,b\},\{a,d\},\{b,d\},\{c,d\},\{a,c,d\},\{b,c,d\}\} 
under $\subseteq$.
\bparts
\ppart Draw the Hasse diagram for this poset.

\begin{picture}(600,400)
\put(100,300){\circle*{5}}
\put(300,300){\circle*{5}}
\put(50,200){\circle*{5}}
\put(150,200){\circle*{5}}
\put(250,200){\circle*{5}}
\put(350,200){\circle*{5}}
\put(100,100){\circle*{5}}
\put(200,100){\circle*{5}}
\put(300,100){\circle*{5}}

\put(100,300){\line(1,-2){50}}
\put(100,300){\line(5,-2){250}}
\put(300,300){\line(-1,-2){50}}
\put(300,300){\line(1,-2){50}}
\put(50,200){\line(1,-2){50}}
\put(150,200){\line(-1,-2){50}}
\put(50,200){\line(3,-2){150}}
\put(250,200){\line(-1,-2){50}}
\put(150,200){\line(3,-2){150}}
\put(250,200){\line(1,-2){50}}
\put(350,200){\line(-1,-2){50}}


\put(80,320){$\{a,c,d\}$}
\put(280,320){$\{b,c,d\}$}
\put(60,200){$\{a,b\}$}
\put(160,200){$\{a,d\}$}
\put(260,200){$\{b,d\}$}
\put(360,200){$\{c,d\}$}
\put(95,80){$\{a\}$}
\put(195,80){$\{b\}$}
\put(295,80){$\{d\}$}
\end{picture}


\ppart Find the maximal elements \\
\{a,b\}, \{a,c,d\}, and \{b,c,d\}.
\ppart Find the minimal elements \\
\{a\}, \{b\}, and \{d\}.
\ppart Is there a greatest element? \\
No.
\ppart Is there a least element? \\
No.
\ppart Find all upper bounds of \{\{b\},\{d\}\}. \\
\{b,d\} and \{b,c,d\}.
\ppart Find the least upper bound of \{\{b\},\{d\}\} if it exists. \\
\{b,d\}.
\ppart Find all lower bounds of \{\{a,c,d\},\{b,c,d\}\}. \\
\{c,d\} and \{d\}.
\ppart Find the greatest lower bound of \{\{a,c,d\},\{b,c,d\}\} if it exists.
\\
\{c,d\}.
\eparts
%GRAPHS

\problem Each of the following sets of people needs to hold a meeting.
Draw a conflict graph for these meetings, and schedule them 
into the smallest possible number of time slots without sending
someone to two meetings at the same time.
\begin{eqnarray*}
C_1 &= &\set{\mbox{Karger},\mbox{Sussman},\mbox{Abelson}}\\
C_2 &= &\set{\mbox{Sussman},\mbox{Ward},\mbox{Minsky}}\\
C_3 &= &\set{\mbox{Karger},\mbox{Minsky},\mbox{Abelson}}\\
C_4 &= &\set{\mbox{Ward},\mbox{Minsky},\mbox{Abelson}}\\
C_5 &= &\set{\mbox{Karger},\mbox{Sussman}}\\
C_6 &= &\set{\mbox{Sussman},\mbox{Minsky},\mbox{Abelson}}
\end{eqnarray*}

\begin{picture}(600,350)
\put(200,280){\circle*{3}}
\put(95,217){\circle*{3}}
\put(95,105){\circle*{3}}
\put(200,42){\circle*{3}}
\put(305,105){\circle*{3}}
\put(305,217){\circle*{3}}

\put(200,300){$C_2$}
\put(75,225){$C_1$}
\put(75,92){$C_6$}
\put(200,20){$C_5$}
\put(315,92){$C_4$}
\put(315,225){$C_3$}

\put(200,280){\line(-5,-3){105}}
\put(200,280){\line(-3,-5){105}}
\put(200,280){\line(5,-3){105}}
\put(200,280){\line(3,-5){105}}
\put(200,280){\line(0,-1){238}}
\put(95,217){\line(1,0){210}}
\put(95,217){\line(2,-1){210}}
\put(95,217){\line(3,-5){105}}
\put(95,217){\line(0,-1){112}}
\put(95,105){\line(2,1){210}}
\put(95,105){\line(1,0){210}}
\put(95,105){\line(5,-3){105}}
\put(200,42){\line(3,5){105}}
\put(305,105){\line(0,1){112}}
\end{picture}

The conflict graph is like the complete graph on these vertices, except it
has no edge between $C_4$ and $C_5$.
The number of slots required for scheduling is the number of colors required
for a valid graph coloring of the conflict graph.
Every pair of vertices in the set $\{C_1, C_2, C_3, C_4, C_6\}$ are
connected by an edge in the conflict graph.  So no two of them can be
colored the same color.  Thus coloring the conflict graph requires at least
5 colors.  The graph can, in fact, be colored with 5 colors by giving each
vertex in the above set one of the colors and assigning $C_5$ the same
color as $C_4$.  Thus the only two vertices that are identically colored
are $C_4$ and $C_5$, and they are not adjacent in the conflict graph.
This corresponds to scheduling $C_1$, $C_2$, $C_3$, and $C_6$ in time
slots by themselves and scheduling $C_4$ and $C_5$ in a common time slot.

\problem Give the adjacency matrix of the graph $W_4$.  How many
(simple or not) paths of length $2$, $3$ and $4$ are there
between the center vertex and each other vertex?

Suppose we number the center vertex 1 and the remaining vertices
consecutively around their common cycle.  Let $A$ be the resulting
adjacency matrix.  Then

\newpage

\begin{tabbing}
Extra space \= ent1 \= ent2 \= ent3 \= ent4 \= ent5 \kill \\
            \> 0    \> 1    \> 1 \> 1 \> 1 \\
           \> 1 \> 0 \> 1 \> 0 \> 1 \\
$A =$      \> 1 \> 1 \> 0 \> 1 \> 0 \\
           \> 1 \> 0 \> 1 \> 0 \> 1 \\
           \> 1 \> 1 \> 0 \> 1 \> 0 \\
\\
\\
           \> 4 \> 2 \> 2 \> 2 \> 2 \\
           \> 2 \> 3 \> 1 \> 3 \> 1 \\
$A^2 =$    \> 2 \> 1 \> 3 \> 1 \> 3 \\
           \> 2 \> 3 \> 1 \> 3 \> 1 \\
           \> 2 \> 1 \> 3 \> 1 \> 3 \\
\\
\\
           \> 8 \> 8 \> 8 \> 8 \> 8 \\
           \> 8 \> 4 \> 8 \> 4 \> 8 \\
$A^3 =$    \> 8 \> 8 \> 4 \> 8 \> 4 \\
           \> 8 \> 4 \> 8 \> 4 \> 8 \\
           \> 8 \> 8 \> 4 \> 8 \> 4 \\
\\
\\
          \> 32 \> 24 \> 24 \> 24 \> 24 \\
          \> 24 \> 24 \> 16 \> 24 \> 16 \\
$A^4 =$   \> 24 \> 16 \> 24 \> 16 \> 24 \\
          \> 24 \> 24 \> 16 \> 24 \> 16 \\
          \> 24 \> 16 \> 24 \> 16 \> 24 \\
\\
\end{tabbing}

As discussed in class, the number of paths of length exactly $k$ from
vertex $i$ to vertex $j$ is the entry in row $i$ and column $j$ of $A^k$.
Thus the number of paths of length 2 between the center vertex and each
other vertex are found in the first column (in the rows corresponding to
these other vertices) of $A^2$.  The number of paths of length 3 and 4
are found in the same positions of $A^3$ and $A^4$, respectively.

\problem Prove that any tree with a degree $k$ vertex has at least $k$
leaves.  

This problem was kind of interesting---3 TAs and the professor came up
with 4 different proofs and couldn't agree on which (if any) was
clear.  So here is a selection.


Note that the statement makes sense for $k = 0$, but is vacuously
true.  Thus, we our proofs will all show the statement to be true for
all positive integers $k$.

{\bf Proof 0:}

Remember that in class we proved that any tree with some edges has
leaf, by considering the endpoints of a maximum-length path.  As was
stated in class, this actually proves that the tree has {\em two}
leaves---one at each end of the path---and we will use this fact.

In this proof, we prove a stronger statement:
Any tree with a vertex, $v$, of degree at least $k$ has at least $k$ leaves,
not counting $v$ (if it happens to be a leaf).
Note that $v$ {\em can't } be a leaf unless $k = 1$.
We don't need to do this strengthening
to make an inductive proof go through, but it makes the proof simpler.

The claim is proven by induction on $k$.  The base case, $k=1$, is
true by the claim that every tree has 2 leaves, so one of them must
not be $v$.  So now let us carry out the inductive step for $k+1$.
Let us suppose there is a tree for which it is not true.  By well
ordering, there is a counterexample tree with the fewest possible
vertices.  Let $v$ be a degree $k+1$ vertex in this tree.  We know
there is a leaf $u$ in $T$ that is not $v$ (as in the base case).
There are two cases to consider.

Case 1: $u$ is a neighbor of $v$.  Suppose we delete $u$ from the
tree.  In this new tree, $v$ has degree $k$.  So (by the inductive
hypothesis) there are $k$ leaves other than $v$.  So if we put $u$
back, we get $k+1$ leaves in $T$, contradicting the claim that we had
a counterexample.

Case 2: $u$ is a neighbor of a different vertex $w$.  Suppose we
delete $u$ from the tree.  In the new tree, $v$ still has degree
$k+1$.  Since we were dealing with the smallest counterexample, the
new tree must have $k+1$ leaves other than $v$.  Now suppose we put
$u$ back.  The only vertex whose degree changes is $w$---so maybe $w$
stops being a leaf.  But we get $u$ as a leaf instead, so we still
have $k+1$ leaves other than $v$.  This contradicts the claim that we
had a counterexample.

This proof was an example of a double induction---we used a separate
(well ordering) induction to prove the inductive step.


{\bf Proof 1:}

In this proof, we prove a stronger statement:
Any tree with a vertex, $v$, of degree at least $k$ has at least $k$ leaves,
not counting $v$ (if it happens to be a leaf).
Note that $v$ {\em can't } be a leaf unless $k = 1$.
We don't need to do this strengthening
to make an inductive proof go through, but it makes the proof simpler.

We use induction on $k$ to prove our stronger statement.

Base Case: For $k = 1$, there is an edge $e$ incident to $v$.
Let $P$ be a maximal simple path containing $e$.
Since $P$ has at least one edge, it has two distinct ends.
Let $w$ be an end of $P$ that is {\em not } $v$.
Then $v$ is adjacent to the next vertex in from it on the path, but
cannot be adjacent to any of the others since this would produce a cycle.
Also, $v$ cannot be adjacent to any vertex not on the path, otherwise
$P$ would not be maximal.
(This argument was already done in lecture).
So $w$ has degree 1 (is a leaf of $T$).

Inductive Step:  Let $k$ be a positive integer and $T$ be a tree with
a vertex, $v$, of degree at least $k + 1$.  Let $u$ be a neighbor of $v$.

Case 1:  $u$ is a leaf.  As shown in class, deleting $u$ and the edge
$(u,v)$ gives another tree $T'$.  In $T'$ $v$ has degree at least $k$.
By the IH, $T'$ has at least $k$ leaves, not counting $v$.
These leaves are neither $u$ nor $v$, so they have the same degree when $u$ and
$(u,v)$ are replaced, making them leaves of $T$ as well.
This also means that when $u$ is also considered,
$T$ has at least $k + 1$ leaves.

Case 2: $u$ is not a leaf.
Let $F$ be the graph that results when $(u,v)$ is deleted from $T$.
This does not create any cycles, so $F$ is a forest.
Also, $u$ and $v$ are in different components of $F$.  Otherwise, there would
be a path (and therefore a simple path) between them not using $(u,v)$.
But that simple path and the edge $(u,v)$ would constitute a cycle in $T$.
The component of $F$ containing $v$ is a tree in which $v$ has degree at
least $k$.
By the IH, this component has at least $k$ leaves, not counting $v$.
(Also, none of them can be $u$, since $u$ isn't in this component).
The component of $F$ containing $u$ is a tree in which $u$ has degree
at least one (since $u$ was not a leaf of $T$ and therefore had degree
at least two in $T$).
By the proof of the base case, this component has at least one leaf, not
counting $u$.
(Also, none of them can be $v$, since $v$ isn't in this component).
Note that even though we are relying on the base case being true, we
are {\em not} using strong induction.  This is because we have an explicit
(direct) proof of the base case.  So we are not making an assumption that
the statement is true for $k = 1$.  Instead, we are using this proof as
a lemma so that we {\em know} the statement is true for $k = 1$.
Since these two collections of leaves come from distinct components of $F$,
they have no leaves in common.
So $F$ must have at least $k + 1$ vertices of degree 1, not counting
{\em either} $u$ or $v$.  Thus these vertices must still have degree 1
when $(u,v)$ is replaced.  So $T$ has at least $k + 1$ leaves, not
counting $v$.

\iffalse

We use strong induction on $k$.
For $k = 0$, the statement is vacuous.
For $k = 1$, the tree must be non-trivial, so it must have a leaf,
as proven in class.

Inductive Step: Consider a tree $T$ with a degree $k>1$ vertex $v$
and let $u_1,\ldots, u_k$ be its neighbors.

If any of the $u_i$ is a leaf then deleting $u_i$  still gives a
tree (as shown in class).  
In this tree, $v$ has degree $k - 1$.  By the
IH, the new tree has at least $k - 1$ leaves.  These leaves must also
be leaves of $T$.  Also considering $u_i$, $T$ must then have at least $k$
leaves.

If none of the $u_i$ is a leaf then all $u_i$ have degree at least 2.
Removing $v$ from $T$ we obtain a forest of $k$ trees, 
each one containing a node $u_i$.
In each tree $u_i$ has degree at least one, and by IH the 
tree has at least one leaf $w_i$.
Since each $w_i$ is also a leaf of the original tree, 
$T$ has at least $k$ leaves.

\fi

\iffalse

For $k = 2$, the tree is still non-trivial and the argument from class
can be trivially adapted to show that both ends of the path are leaves.

Inductive Step:  Consider a tree $T$ with a degree $k$ vertex $v$ where $k > 2$.
Let $u$ be a neighbor of $v$.
Case 1: $u$ is a leaf.  Then deleting $u$ and its neighbor still gives a
tree (as shown in class).  In this tree, $v$ has degree $k - 1$.  By the
IH, the new tree has at least $k - 1$ leaves.  These leaves must also
be leaves of $T$.  Also considering $u$, $T$ must then have at least $k$
leaves.
Case 2: $u$ is not a leaf.  Then $u$ has degree at least 2 in $T$.  None
of these other edges incident to $u$ can connect to $v$, of course.  So
we can delete the $k - 1$ edges incident to $v$ other than $(u,v)$.
and still have $u$ have degree at least 2 in the resulting graph.  Since
this does not create cycles, this graph is a forest.  Thus the component
containing $u$ is a tree.  By the IH, this component has at least 2 leaves.
At least one of them must not be $u$.  Call this leaf $w$.  Note $w$ has
a simple path to $v$ in this component.  But $v$ is adjacent only to $u$
in this graph, so the simple path contains $(u,v)$.  This simple path is
also found in $T$.  So it must be the unique simple path between $u$ and $v$
in $T$.  Thus removing $(u,v)$ from $T$ disconnects $u$ from $v$  (because
the existence of another path would imply the existence of a cycle).
But removing $(u, v)$ creates a forest (since it does not create any cycles)
in which $v$ has degree $k - 1$.  By the IH, the component (a tree) containing $v$
in the new graph at least $k - 1$ leaves.
Clearly these leaves are also leaves of $T$, as is $w$.  So $T$ has at least
$k$ leaves.

\fi

Proof 2:

Let $T$ be a tree containing a vertex $v$ of degree $k$.
For each edge $e$ incident to $v$, let $P_e$ be a maximal simple path
containing $e$.
Define a function $f$ from the edges incident to $v$ to the leaves of $T$
by letting $f(e)$ be the end of $P_e$ that you reach by starting at $v$,
following $e$, and continuing along $P_e$.  So $f(e)$ is connected to $v$
in $T$ by a simple path containing $e$.  Clearly $f(e)$ cannot be connected
to $v$ in $T$ by a simple path containing any other edge $e'$ incident to
$v$, since this would create a cycle.  This verifies that $f$ is an
injective map from the edges incident to $v$ to the vertices of $T$.
It was shown in class that the end of a maximal simple path in a tree is
a leaf of that tree, so $f$ does indeed map to the leaves of $T$.  Since
$f$ is an injection, the number of leaves of $T$ is at least the number
of edges incident to $v$, which is $k$.

\problem
What is wrong with the following ``theorem'' and ``proof?''\\
{\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\
{\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\
Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\
Inductive step. Assume $P(n)$ is true. Now, take any graph with $n$
vertices with minimum degree at least one and add a new vertex to
it. By inductive hypothesis the graph on $n$ vertices is
connected. Since the new vertex satisfies the assumption it must have
degree at least one, so it must have an edge connecting it to one of
the remaining $n$ vertices. Thus the whole graph is connected. Hence
$P(n+1)$ is true. Thus, $P(n)$ is true for all $n$.  

\bigskip

The proof has buildup error. In the inductive step instead of considering a
graph with $n+1$ vertices, a vertex is added to a pre-existing graph of $n$
vertices.  It is not true however, that any $n$-subgraph of a graph with $n+1$ 
vertices of degree at least one, has also vertices of degree at least one.
Consider for example the graph of $4$ vertices consisting of two disjoint 
line segments.

\bigskip

\end{problems}

\noindent The next problems are going to prove an interesting fact
about graphs that that can be colored with two colors.  These graphs
are called {\em bipartite} because you can divide them into two groups
(colors) such that every edge has one endpoint in each group.  We
prove:

\begin{theorem}
A graph is bipartite if and only if it contains no cycles of odd
length.
\end{theorem}

It is enough to prove this theorem for a connected graph, because then
we can apply it separately to each component of an arbitrary graph.

\begin{problems}


\problem Prove that a graph contains an odd-length circuit if and only
if it contains an odd length cycle (hint: consider the shortest odd
length circuit).


If a graph contains an odd-length cycle, then obviously it contains an 
odd-length circuit (the cycle itself).

Now suppose that the graph contains an odd-length circuit, and consider an
odd-length circuit of minimum length (say $n$).  If it is a cycle then we are done.
Suppose, to arrive at a contradiction, that the circuit is not a cycle. Then
some vertex $\bar{i}$ (other than the initial) is repeated. The circuit has the
form
$$
(i_1,i_2),\ldots,(i_k,\bar{i}),\ldots,(\bar{i},i_l),\ldots,(x_n,x_1)
$$

Consider the circuits
$(i_1,i_2),\ldots,(i_k,\bar{i}),(\bar{i},i_l),\ldots,(x_n,x_1)$ and
$(\bar{i},i_{k+1}),\ldots,(i_{l-1},\bar{i})$.

Their lengths are less than $n$, and since the sum of their lengths is odd, one of them has odd length.  So we have a smaller circuit of odd length and we 
obtain a contradiction.

\bigskip

\problem Prove that if $G$ is bipartite then it contains no circuits
 of odd length.

Let $G$ be bipartite and suppose that it has a circuit of length $2n+1$.
Then (by pigeonhole) there are $n+1$ nodes of the same color, so two of them
 must be adjacent. Thus we obtain a contradiction.
  

\bigskip

\problem Suppose $G$ is a connected graph with no odd cycles (or
circuits).  Fix a particular vertex $u$.  
\begin{problemparts}
  \problempart Prove that for any vertex $v$, the length of every path
  from $u$ to $v$ is odd or the length of every path from $u$ to $v$
  is even.

Let $p1$ and $p2$ be two paths connecting $u$ and $v$.  If one has odd length
and the other even, than the concatenated path is an odd cycle. This
contradicts the hypothesis.


  \problempart Suppose I color a vertex according to the odd/evenness of its
  paths from $u$.  Prove this is a legal coloring.  Deduce that $G$ is
  bipartite.

Suppose $v$ has even color.  Then there is an odd length path (through $v$)
to each of its
neighbors, so they have odd color.
Analogously, if $v$ has odd color, all its neighbors must have even 
color because they can be reached from $u$ via an even length path (through
$v$).

\end{problemparts}

\problemopt Suppose we are in a connected maze (undirected graph) and
explore it according to the following rules:
\begin{enumerate}
\item Never traverse an edge more than once in each direction
\item The first time we enter a room, mark our entering edge.  Do
  not use the entering edge to exit a room unless it is the only
  remaining choice under the first rule.
\end{enumerate}
Prove that we get stuck (can't apply either rule) only at our starting
point, and that by then every edge has been traversed in both
directions.

\bigskip

First we show that we can only get stuck at the origin.
For any vertex $i$, let $index(i)$ denote the number of unused incoming edges minus the
number of unused outgoing edges.  We claim the following invariants.

For any node $i$ that is not the starting point, 
$$
index(i) = 
\{
\begin{array}{cc} -1 & \mbox{if we are in } i  \\ 
0 & \mbox{otherwise} \end{array}
$$

while for the starting point $o$ we have
$$
index(o) = 
\{
\begin{array}{cc} 0 & \mbox{if we are in } o  \\ 
1 & \mbox{otherwise} \end{array}
$$

These invariants are easily proved by induction on the number of 
traversed edges.

Base case: if no edge has been traversed yet, then we are in $o$ and
$index(n)=0$ for all nodes because all edges have been used 
neither to enter nor to exit any given node.

Inductive step: assume that after $n$ edges have been traversed 
the invariant hold true. We traverse one more edge $(v,w)$.
$index(v)$ is incremented by one, and $index(w)$ is 
decremented by one. 
A simple case analysis show that if the invariant is true 
before $(v,w)$ is traversed, then it is true 
also after traversing that edge.

\iffalse 

The base cases (0 visits) is obvious.  Now suppose the claim holds for $n$ visits. On the $n+1$th visit to node $i$, I decrement it's index by 1. By 
the inductive hypothesis it was 0, so now it becomes -1.  This implies that 
there is an exit available (otherwise the index would be 0,or 1), so I exit 
and the index becomes 0 again.
The proof for the origin is similar.

\fi

We can only get stuck in a node $v$ only if all edges of this node have 
been traversed in the outgoing direction.
But in this case $index(n)\leq 0$. This is possible only if 
$n$ is the starting node, since otherwise $index(n)=-1$. 
This proves that we can only get stuck at $o$.

Suppose, to obtain a contradiction, that $(i,j)$ is an edge that has not been
traversed in both directions.  Then node $i$ must also have an incomming
edge which is also an unused outgoing edge (because it's index is $0$).  
We can assume without loss of generality
that this edge is marked (because the marked edge is the last one to be used
 as an exit).  Since a marked edge indicates a first visit, and we started at 
$o$, 
there is a path of incomming edges from $i$ to $o$.  So $o$ has an outgoing 
edge. If $o$ has no other unbalanced edge, then the index of $o$ is not $0$ which is a contradiction.  So $o$ must have an incomming edge that is unused as an outgoing edge.  But this contradicts the assumption that we are stuck, 
since we can use it as an outgoing edge.
 
\end{problems}

\end{document}

















% Local Variables: 
% mode: latex
% TeX-master: t
% End: 



