\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.
\ppart Find the maximal elements
\ppart Find the minimal elements
\ppart Is there a greatest element?
\ppart Is there a least element?
\ppart Find all upper bounds of \{\{b\},\{d\}\}.
\ppart Find the least upper bound of \{\{b\},\{d\}\} if it exists.
\ppart Find all lower bounds of \{\{a,c,d\},\{b,c,d\}\}.
\ppart Find the greatest lower bound of \{\{a,c,d\},\{b,c,d\}\} if it exists.
\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*}

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

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

\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 ciruit (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,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 colour, 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 concatinated path is an odd cycle. This
contradicts the hypothesis.


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

Suppose $v$ has even colour.  Then there is an odd length path to each of its
neighbors, so they have odd colour.


\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 sum of incomming edges minus the
sum of outgoing edges.  We claim the following invariants.

For any node $i$ that is not the starting point, 
$$
index(i) = 
\{
\begin{array}{cc} +1 & \mbox{after entering } i  \\ 
0 & \mbox{after leaving } i\end{array}
$$

while for the starting point $o$ we have
$$
index(o) = 
\{
\begin{array}{cc} 0 & \mbox{after entering } i  \\ 
-1 & \mbox{after leaving } i\end{array}
$$

These invariants are easily proved by induction on the number of visits to the node.  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.

We can only get stuck in a node only if all edges of this node have been 
traverced in both directions or if there are only outgoing edges, i.e if the
index is $0$ or $-1$ after entering. But the only node with this property is
the starting point.

Now we prove that when we're stuck, each edge has been traversed twice.
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 a free incomming
edge (because it's index is $0$).  We can assume without loss of generality
that this edge is marked (becasue 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, which contradict either the fact that it's index is 0, or the assumption
that we are stuck.
 
\end{problems}

\end{document}

















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



