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

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

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

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

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

\end{problems}

\end{document}

















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



