\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
%
  \newcommand{\handoutlabel}{sol4}
  \newcommand{\handouttitle}{Problem Set 4 Solutions}
  \newcommand{\handoutdate}{February 29, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{}
%
  \newcommand{\handoutlabel}{ps4}
  \newcommand{\handouttitle}{Problem Set 4}
  \newcommand{\handoutdate}{February 22, 2000}
  \newcommand{\duedate}{February 29, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{\pset{3}{\handoutdate}{2:35pm in lecture, \duedate}}
%
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%\handout{\handoutlabel}{\handouttitle}{\handoutdate}

%\pset{3}{February 15, 2000}{2:35pm in lecture, February~24, ~2000}

\titlebar

\reading{%

\textbf{Self-Study Reading:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Section 7.3
\end{description}

\textbf{Note:} The self-study reading covers basic mathematical topics
that we assume you are familiar with and that will not be explicitly
covered in the lectures.  We recommend that you skim them over and
encourage you to discuss any topics that are unclear to you with your
TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Self-Study Problems:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Section 7.3, exercises 3, 7, 11, 26, 35, 43
\end{description}

\textbf{Note:} The self-study problems are intended for you to get
some practice on the mathematical topics covered by the self-study
reading.  Again, make sure that you understand the concepts presented
in the problems and that you discuss any topics that are unclear to
you with your TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Reading:}
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Graphs: Sections 7.4, 7.5, 7.8;
  Trees: Section 8.1;
  Computational Processes: Rosen 7.1;
\item[6.042 Fall 97 Lecture notes (available from course page):] \mbox{} \\ %
  Graphs: Lecture 4 handout;
  Trees and Dags: Lecture 5 handout;
\end{description}

}

\textbf{Required Problems:}

\vspace*{0.5\baselineskip}

\collaboration

%%%%%%%%%%%% BEGIN PROBLEMS %%%%%%%%%%%

\problem \textbf{Graph Coloring}

Argue that a graph is 2-colorable if and only if every simple cycle is of
even length.

\omitsolution{
\begin{solution}
Assume a graph has a simple cycle of odd length.  Let the cycle be
$v_1,v_2,\ldots, v_n,v_1$, where $n$ is odd. Suppose that two colors
(red and blue) sufficed to color the graph containing this circuit.
Without loss of generality let the color of $v_1$ be red. Then $v_2$
must be blue, $v_3$ must be red, and so on, until finally $v_n$ must
be red (since $n$ is odd). But this is a contradiction, since $v_n$ is
adjacent to $v_1$.  Therefore at least three colors are needed. Hence
a graph is 2-colorable only if every simple cycle is of even
length. Conversely, assume the graph has no simple cycle of odd
length. We show that it is possible to color the graph using two
colors. Without loss of generality, assume that the graph is
connected. (As otherwise we can repeat the argument for each connected
component of the graph). Select a node, say $m$, in the graph and
color it red. Color all the nodes adjacent to $m$ blue. (Call the set
of all such nodes $S_1$.) Color all the nodes that are adjacent to the
nodes in $S_1$ but have not yet been colored, red. (Call the set of
all such nodes $S_2$.)  Continue this process until you have colored
all the nodes. We now show that no two nodes in $S_i$ are connected by
an edge, for all $i$.\footnote{This is sufficient to establish that
our coloring is valid, since by construction we cannot have two
adjacent nodes that were colored identically but do not belong to the
same set $S_i$.} Assume that we can find two nodes $u$ and $w$ in some
set $S_i$ that are adjacent in the graph. If $u$ and $w$ are adjacent
to a node in $S_{i-1}$ then we have a simple cycle of length $3$,
which is impossible.  So let $u_{i-1}\neq w_{i-1} \in S_{i-1}$ be
nodes adjacent to $u$ and $w$ respectively.  Now if $u_{i-1}$ and
$w_{i-1}$ are adjacent to a single node in $S_{i-2}$, say $c$, then
$u,u_{i-1},c,w_{i-1},w,u$ is a simple cycle of length 5, which is
impossible.  So let $u_{i-2}\neq w_{i-2}\in S_{i-2}$ be nodes adjacent
to $u_{i-1}$, and $w_{i-1}$ respectively. Continuing this way we
arrive at nodes $u_1\neq w_1 \in S_1$. However these are adjacent to
$m$.  But this gives us a simple cycle
$m,u_1,u_2,\ldots,u_{i-1},u,w,w_{i-1},w_{i-2}\dots,w_1,m$, where
$u_j,w_j\in S_j$. But this cyle has length $2 i+1$, which is odd,
hence a contradiction. Therefore, for all $i$ we do not have two nodes
in $S_i$ that are connected by an edge.  Therefore our coloring is
valid.  
\end{solution}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf graph coloring; trivial with previous problem, more
  challenging by itself.}

A graph is said to be bipartite if it is $2$-colorable. Show that every tree is bipartite. (Hint: first show that every tree has a leaf.)
\omitsolution{
\begin{solution}
\emph{not done yet}
\end{solution}
}


\problem {\bf Euler-tourish} 

Let $G$ be a graph.  Prove that there is
a path from every vertex of odd degree to some other vertex of odd
degree.

\omitsolution{
\begin{solution}
If graph $G$ has no vertex of odd degree, then the claim is true
vacuously.  Otherwise, let $v$ be a vertex of odd degree.  Consider a
longest path starting at $v$ in which each edge occurs at most once.
Then every edge leaving the final vertex on the path must already be
on the path.  We will show that this final vertex of the path is
another vertex of odd degree.

Since $v$ has odd degree, the path contains at least one edge.
Furthermore, the final vertex of the path cannot be $v$, since the
edges incident to $v$ would then consist of the first and last edge of
the path plus two edges for each time that the path crosses $v$--- an
even total.  Therefore, the edges incident to the final vertex of the
path consist of the final edge of the path plus two edges for each
time that the path crosses the final vertex--- an odd total, as
claimed.
\end{solution}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf Basic Graph Stuff} 

An edge of a connected graph is called a {\em cut-edge} if removing
the edge disconnects the graph.  Prove that an edge $e$ in a connected
graph $G$ is a cut-edge if and only if no simple cycle contains $e$.

For this problem, use the definition of a ``simple cycle'' given on
page 468 of Rosen (p.463 in ed.3).  (The lecture notes require a
simple cycle to have no repeated vertex, but Rosen requires no
repeated edge.)

\omitsolution{
\begin{solution}
First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.  (Which sequence is
substituted for edge $e$ depends on the direction in which the path
$P$ traverses the edge $e$.)  This shows that the graph remains
connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{solution}
}

\problem {\bf Basic graphs; proofs}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {Hamiltonian Paths}

A \defi{hamiltonian path} in an undirected graph is a simple
path that visits all the vertices.  An undirected graph is said to be
\defi{hamiltonian} if there exists a simple cycle that contains all
the vertices.  Let $A$ be the adjacency matrix of an undirected
graph~$G$, where we assume $A[v,v]=1$ for all $v\in V$.  The
\defi{cube} of $G$ is the graph $G^3=(V,E^3)$ whose adjacency matrix
is $A^3$, where we perform matrix multiplication using the boolean
operations $\vee$ and $\wedge$ instead of the usual $+$ and $\times$.
The aim of this problem is to show that the cube of any connected
graph is hamiltonian.

%\begin{problemparts}

\problempart Prove that any connected graph contains a free tree that
connects all the vertices as a subgraph.

\problempart Argue briefly that $(u,v)\in E^3$, or equivalently, that
$A^3[u,v]=1$, if and only if the distance between $u$ and $v$ in $G$
is at most~$3$.

\problempart Prove by induction that the cube of any rooted tree
contains a hamiltonian path that begins at the root and ends at one of
its children.

\problempart Prove that the cube of any free tree is Hamiltonian, and
conclude that the cube of any connected graph is Hamiltonian.

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



\problem {\bf Average of neighbors}

Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$
be a function associating a real number with each vertex.  Suppose $r$
satisfies the property that for each $v\in V$, the value $r(v)$ is the
average of the values of $v$'s neighbors.  Prove that if the graph is
connected, then $r(u)=r(v)$ for all $u,v\in V$.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Connectivity false proof}

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 %%%%%%%%%%%%%%

\problem {\bf Tangled Graphs}
% topic: tangled graphs
% source: fall98 pset3 Problem 6

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.

\emph{{\bf Theorem?}} Every non-empty, tangled graph is connected.

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

\omitsolution{
\begin{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)'.
\end{solution}
}


\problempart Draw a tangled graph that is not connected.

\omitsolution{
\begin{solution}
\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{ps3-tangled-cx.eps}}}
\end{figure}
\end{solution}
}

\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 that every non-empty, mangled graph
is connected.

\omitsolution{
\begin{solution}
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{solution}
}

%\end{problemparts}

\problem {\bf Algorithmic Proof}
%(Problem adapted from F97 pset 4)

The following algorithm can be used to multiply any two natural
numbers $x$ and $y$. 
The answer is accumulated in variable $a$;
variables $r$ and $s$ are for temporary storage. 

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\kill
$r:=x$; \\
$s:=y$; \\
$a:=0$;\\
do until $s=0$:\\
   \>if s is even then \\
   \>\>   $r := 2r$; \\
   \>\>   $s := s/2$;\\
   \>else \\
   \>\>   $a := a + r$; \\
   \>\>   $r := 2r$; \\
   \>\>   $s := (s-1)/2$;\\
\end{tabbing}
The answer $xy$ is the value left in the accumulator $a$ when the 
procedure terminates.

\problempart Model the algorithm as a state machine.  
That is, define the states $Q$, the start states $Q_0$, and the steps
$\delta$.

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

\problempart List the sequence of states that appears in an execution of the
algorithm for inputs $x=5$ and $y=9$.

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

\problempart Prove that the algorithm gives the correct answer if it
terminates, that is, that $s = 0$ implies $a = xy$.
(Hint:  Use induction on the number of steps in the execution.  You
will have to strengthen the inductive hypothesis.)

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

\problempart Prove that the algorithm terminates. 

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

\problem {\bf Minimal elements of posets}

\problempart Let $(S,R)$ be a poset.  Show that $(S, R^{-1})$ is also
a poset, where $R^{-1}$ is the inverse of $R$.

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

\problempart Prove by induction that any finite poset has a minimum element.

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

\problempart Combining the previous two parts, prove that every poset has a
{\em maximal} element that is not less than or equal to any other.

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

%\end{problems}
\end{document}

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