\problem

What is wrong with the following ``theorem'' and ``proof?''\\
\emph{{\bf Theorem?}} If every vertex in a graph has degree at least one then the graph is connected.
\begin{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 on $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{proof}

\omitsolution{
\begin{solution}
\emph{not done yet.}
\end{solution}
}



\problem
A graph is said to be planar if it can be drawn on the plane so that edges do not cross each other. Take the following fact for granted:  every planar graph contains at least one node of degree at most $5$. Now prove that any planar graph can be $6$-colored.



%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%

\problem 
% topic: posets, total orders, linear extensions
% source: fall98 pset3 Problem 4

A {\em linear extension} of a poset is a
total order consistent with the partial order.  That is, if $x > y$ in
the partial order, then $x > y$ in the total order also.  For example,
in the poset defined by the Hasse diagram below, the following
relationships hold: $a > b$, $a > c$, $a > d$, $a > e$, $b > c$, and
$b > d$.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial.eps}}}
\end{figure}

This poset has eight linear extensions, which are listed in the table below.  
To
clarify the notation, the upper-left entry represents the total order
where $a$ is the largest element, $b$ the second largest, and so
forth.  Note that all of the relationships that hold in the poset also
hold for all the total orders listed below.

\[
\begin{array}{ccc}
a > b > c > d > e       & \quad \quad &         a > b > d > c > e \\
a > b > c > e > d       &       &               a > b > d > e > c \\
a > b > e > c > d       &       &               a > b > e > d > c \\
a > e > b > c > d       &       &               a > e > b > d > c
\end{array}
\]

%\begin{problemparts}

\problempart List all the linear extensions of the poset represented by the
Hasse diagram below.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial2.eps}}}
\end{figure}

\omitsolution{%
\omitsolution{
\[
\begin{array}{ccc}
a > b > c > e > d       & \quad \quad &         a > c > b > e > d \\
a > b > c > d > e       &       &               a > c > b > d > e \\
a > b > d > c > e
\end{array}
\]
}
}

\problempart  After considering the above examples, Math Moose formulated
the following claim.

\bigskip

{\bf Claim.} The number of linear extensions of a partially ordered
set with $n$ elements always divides $n!$.

\bigskip

Either prove that his claim is correct for all posets or else draw
the Hasse diagram of a counterexample and list all linear extensions.

\bigskip

\omitsolution{%
\omitsolution{
The claim is false.  The 4-element poset depicted below has 5 linear
extensions.  This is a counterexample, because 5 does not divide 4!.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-poset-cx.eps}}}
\end{figure}

\[
\begin{array}{ccc}
a > b > c > d   & \quad \quad &         a > b > d > c \\
b > a > c > d   &       &               b > a > d > c \\
b > d > a > c
\end{array}
\]
}
}

%\end{problemparts}


%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%

\problem 
% topic: automorphism and graphs
% source: fall98 pset3 Problem 5

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}[htbp]
\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}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-findauto.eps}}}
\end{figure}

\omitsolution{%
\omitsolution{
\[
\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.

\omitsolution{%
\omitsolution{
\begin{figure}[htbp]
\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-noauto.eps}}}
\end{figure}
}
}

%\end{problemparts}


%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%

\problem 
% topic: Towers of Hanoi, induction
% source: spring00 tut2 proposed

\emph{The Towers of Hanoi.}

There are three poles.  On the first pole there is a stack of rings of
increasing size, with the smallest ring on top of the stack.  The
second and third poles are empty.  The challenge is to move the entire
stack of rings to the second pole, while obeying the following rules:
\begin{itemize}
\item ~~Rings may only be moved one at a time from one pole to another.
\item ~~A ring may only be moved if it is on the top of a stack.
\item ~~A ring may only be placed on top of a larger ring.
\end{itemize}

Suppose there are $n\ge 1$ rings initially stacked on the first pole
and rings are only moved according to these rules.

%\begin{problemparts}

\problempart Prove that no matter how many moves are made, the rings 
stacked on each pole, if any, increase in size from the top.

\omitsolution{%
  \begin{proof}
    The proof is by induction on the number of moves~---~not the
    number of rings.

    Let $P(k)$ be the predicate: ``After $k$ moves, the rings stacked
    on each pole increase in size from the top.''  The base case
    $P(0)$ follows because initially, that is, after zero moves, the
    rings are in increasing order.

    Now assume $P(k)$, namely, that they are in order on every pole
    after $k$ steps.  Suppose on the $k+1$st move ring $R$ is moved
    from pole $i$ to pole $j\neq i$.  Then the rings left on pole $i$,
    if any, are still in order.  Also, the ring that was on top of
    pole $j$, if any, must be larger than $R$ according to the rules,
    so the rings on pole $j$ increase in size starting from ring $R$
    on top.  Of course the rings on the remaining pole, if any, are
    unchanged, and so remain in increasing order.  Hence all poles
    have rings in increasing order from the top after $k+1$ moves,
    that is, $P(k+1)$ holds.
  \end{proof}
}

\problempart Prove (by giving and analyzing a recursive algorithm)
that there is a way to move all the rings to the second pole in
$2^n-1$ moves.

\omitsolution{%
  \begin{proof}
    The proof is by induction on the number of rings $n$.  However, in
    order to simplify the proof, we strengthen the induction
    predicate.  In particular, we allow there to be $n$ \emph{or more}
    rings initially stacked in increasing order on \emph{any} given
    pole~---~not necessarily the ``first'' pole.

    Let $P(n)$ be the predicate: ``For $i \in \set{1,2,3}$, suppose
    there are $n \geq 1$ or more rings stacked on pole $i$ in
    increasing order from the top.  Suppose also that the rings, if
    any, on top of the other two poles are larger than the top $n$
    rings stacked on pole $i$.  Then, the top $n$ rings stacked on
    pole $i$ can be moved to any other pole in $2^n-1$ legal steps.''

    Notice that it follows as a special case of $P(n)$, that $n$ rings
    stacked in order on pole 1 can be moved to pole 2 in $2^n-1$ legal
    steps, as required.

    Now we prove $P(n)$ by induction on the number of rings $n$.
    Without loss of generality, let $i$ denote the pole on which the
    $n$ rings are stacked initially, $j$ denote the pole on which we
    must move the $n$ rings initially stacked on pole $i$, and $k$
    denote the remaining pole.
    \begin{description}\itemsep 0ex
    \item[Base Case:] \mbox{} \\ %
      $P(1)$ is true if the ring on top of pole $j$, if any, is larger
      than the ring on pole $i$, then the single ring on pole $i$ can
      be moved in $2^1-1 =1$ legal step onto pole $j$.
    \item[Inductive Step:] \mbox{} \\ %
      Assume $P(n)$ holds for some integer $n \ge 1$.
      
      Now, we must prove that $P(n+1)$ holds.  We assume that there
      are $n+1$ rings stacked in increasing order on pole $i$ and that
      the rings on the other two poles are larger than the top $n+1$
      rings stacked on pole $i$.  By the induction hypothesis, we can
      move the top $n$ rings from pole $i$ to pole $k$ in $2^n-1$
      moves.  Subsequently, it is legal to move the top ring on pole
      $i$, which is the $n+1$th ring initially stacked on pole $i$,
      from pole $i$ to pole $j$.  Finally, by the induction hypothesis
      we can move the top $n$ rings stacked on pole $k$ to pole $j$ in
      $2^n-1$ more steps.  Concluding, we have succeeded to move the
      top $n+1$ rings from pole $i$ to pole $j$ in a total of $(2^n-1)
      + 1 + (2^n-1) = 2^{n+1}-1$ legal moves; that is, we have shown
      that $P(n+1)$ is true.
  \end{description}
  \end{proof}
}

\problempart Prove that the number of moves necessary to move all $n$ rings
from the first pole to the second is \emph{at least} $2^n-1$.

\omitsolution{%
  \begin{proof}
    The solution to this part is similar to the solution to part (b).
    The key is in realizing that when the $n+1$st largest ring on pole
    $i$ is first moved to pole $j$, the $n$ rings stacked initially on
    top of pole $i$ must, by part~(a), appear in increasing order on
    pole $k$.  Thus, by the induction hypothesis at least $2^n-1$
    moves must have occurred already.  Similarly, at least another
    $2^n-1$ moves are needed after the $n+1$st ring is placed on pole
    $j$ in order to move the $n$ rings from pole $k$ to pole $j$.
  \end{proof}
}

%\end{problemparts}

\problem Prove that edges of any connected, undirected graph with an
even number of edges can be oriented (given a direction) so that every
vertex has even out-degree.

\problem Let us associate a ``weight'' $w(x)=2^{-d}$ with each leaf of
depth $d$ in a binary tree~$T$.  Use the structural induction
definition of a binary tree on page 94 of Handout~\ref{clrchap5} to
prove the \defn{Kraft Inequality}: $\sum_x w(x) \leq 1$, where the sum
is taken over all leaves $x$ in~$T$.  (Beware of ``build-up error''
[MR, p.~173].)

\problem Prove that each vertex of an undirected graph can be colored
red or grey such that every vertex is connected to at least as many
neighbors of the opposite color as it is to neighbors that are the
same color as itself.

\problem Each vertex of an undirected graph $G=(V,E)$ contains a
toggle switch and a lightbulb.  If you push the toggle switch in a
vertex, the bulb in the vertex goes off if it was on, and on if it was
off.  Moreover, all the bulbs in neighboring vertices are toggled as
well.

Initially, all the bulbs are off.  Notice that pushing the same switch
twice doesn't affect any of the bulbs.  Hence, we can talk of a
``setting'' of the switches, which corresponds to the subset of
vertices whose switches have been pushed once (or an odd number of
times).  The aim of this problem is to prove that for any undirected
graph $G$, there exists a \defi{good} setting of the switches: a
setting such that all the bulbs are turned on simultaneously.

%\begin{problemparts}

\problempart Suppose that $G$ has an even number $\card{V}$ of
vertices.  Prove that if every graph on $\card{V}-1$ vertices has a
good setting, then a good setting for $G$ can be obtained by combining
(in some suitable way, which you have to come up with) the settings
corresponding to the subgraphs induced (see Handout 9, page 88) by the
$\card{V}$ subsets of $V$ that have $\card{V}-1$ vertices.

\problempart Suppose that $G$ has an odd number of vertices.  Prove
that there exists a vertex with even degree.

\problempart Suppose that $G$ has an odd number of vertices, let $v$
be an even-degree vertex, and let $S$ be the set of vertices that
includes $v$ and its neighbors.  Prove that if every graph on
$\card{V}-1$ vertices has a good setting, then a good setting for $G$
can be obtained by combining the settings corresponding to the
subgraphs induced by some $\card{V}-\card{S}$ subsets of $V$ that have
$\card{V}-1$ vertices.

\problempart Conclude that a good setting exists for any undirected
graph.

%\end{problemparts}


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