\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}


%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions
\showsolutions

\newcommand{\shorter}{\vspace{-0.3cm}}

\renewcommand{\reading}{The reading is from Rosen.  The assignment is
tailored carefully in order to save you work.  You may, of course,
read more about concepts that you find confusing.

\begin{itemize}

\shorter \item \S8.1 - Read through definition 4.

\shorter \item \S8.2 - Read through example 11.

\shorter \item \S8.3 - Read "Adjacency Matrices" through Example 4 and "Isomorphism of Graphs" through Example 10.

\shorter \item \S8.4 - Read through Example 10.

\shorter \item \S8.5 - Read "Euler Paths and Circuits" through Theorem 1 and "Hamiltonian Paths and Circuits" through Example 5.

\shorter \item \S8.7 - Read through Example 4. Also read "Kuratowski's Theorem".

\shorter \item \S8.8 - Read through Example 3.

\shorter \item \S9.1 - Read through Example 2. Also read Theorem 2 and its proof.

\end{itemize}
}

\begin{document}

\problemset{3}

\graphicspath{{/toc/a/class/6.042/fall02/problemrepository/figures/}}

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

\begin{problem}
In a simple graph, a vertex $u$ is said to be {\em connected to} a
vertex $v$ if $u = v$ or there is a path from $u$ to $v$.

\begin{problemparts}

\problempart Show that ``connected to'' is an equivalence relation on
the vertices in an undirected graph.

\solution{We show that the ``connected to'' relation is reflexive,
symmetric, and transitive.  This implies that ``connected to'' is an
equivalence relation.

For simplicity, suppose that there is a path of length 0 from every
vertex to itself.  Thus, $u$ is connected to $v$ if and only if there
is a path from $u$ to $v$.

\begin{description}

\item[reflexive] Every vertex $v$ is connected to itself, since there
is a path from every vertex to itself.

\item[symmetric] Suppose that vertex $u$ is connected to vertex $v$.
Then there is a path from $u$ to $v$.  Reversing this sequence of
edges gives a path from $v$ to $u$.  Therefore, $v$ is connected to $u$.

\item[transitive] Suppose that $u$ is connected to $v$ and $v$ is
connected to $w$.  Then there is a path from $u$ to $v$ and a path
from $v$ to $w$.  Concatenating these sequences of edges gives a path
from $u$ to $w$.  Therefore, $u$ is connected to $w$.

\end{description}
}

\problempart What are the equivalence classes defined by this
relation?

\solution{Each equivalence class consists of all the vertices in a
connected component of the graph.}

\end{problemparts}

\end{problem}

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

\begin{problem} Suppose the number of 6.042 recitations is decreased
to 8, but there are two TAs at each recitation and the lecturers help
out with several of the larger sections.  The assignment of course
staff to recitation sections is as follows:

\begin{itemize}
\item R1:  Karen, Mana, Eric \\
\item R2:  Karen, Kilian, Albert\\
\item R3:  Mana, Ching\\
\item R4:  Edmond, Kilian, Eric\\
\item R5:  Edmond, Min, Albert\\
\item R6:  Min, Ching\\
\item R7:  Min, Kilian\\
\item R8:  Mana, Ching, Albert
\end{itemize}

Two recitations can not be held in the same 90-minute time slot if
some staff member is assigned to both recitations.  We want to
determine the minimum number of time slots required to complete all
the recitations.

\begin{problemparts}

\problempart Recast this problem as a question about coloring the
vertices of a particular graph.  Draw the graph and explain what the
vertices, edges, and colors represent.

\solution{Each vertex in the graph below represents a recitation
section.  An edge connects two vertices if the corresponding
recitation sections share a staff member and thus can not be scheduled
at the same time.  The color of a vertex indicates the time slot of
the corresponding recitation.

\begin{center}
\includegraphics[height=2in]{ps3-schedule}
\end{center}
}

\problempart{Show a coloring of this graph using the fewest possible
colors.  What schedule of recitations does this imply?}

\solution{At least four colors are needed.  One possible coloring is
shown below:

\begin{center}
\includegraphics[height=2in]{ps3-schedule-colored}
\end{center}

This corresponds to the following assignment of recitations to four
time slots:

\begin{enumerate}

\item R1, R5

\item R2, R3

\item R4, R6

\item R7, R8

\end{enumerate}

Other schedules are possible.
}

\end{problemparts}

\end{problem}

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

\begin{problem}
Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the Cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  Your
diagram must be tidy to receive full credit.  In particular, label all
the vertices, e.g., $(b, 3)$, and use two different colors or line
styles (e.g., dashed and solid) to distinguish the two types of edge
defined above.

\begin{center}
\includegraphics[height=1in]{ps3-twographs}
\end{center}

\solution{
  \begin{samepage}
    \begin{center}
      \includegraphics[height=2in]{ps3-product}
    \end{center}
  \end{samepage}
}

\problempart Show that $G \times H$ is connected if and only if both
$G$ and $H$ are connected.

\solution{$\Leftarrow$ Suppose that $G$ and $H$ are connected.  We
will show that $P = G \times H$ is connected.  Let $(v_1, w_1)$ and
$(v_2, w_2)$ be vertices in $P$.  Since $G$ is connected, there is
path from $(v_1, w_1)$ to $(v_2, w_1)$ using only edges of the first
type.  Since $H$ is connected, there is a path from $(v_2, w_1)$ to
$(v_2, w_2)$ using only edges of the second type.  Concatenating these
paths gives a path between $(v_1, w_1)$ and $(v_2, w_2)$.  Thus, there
is a path between every pair of distinct vertices in $P$, and so $P$
is connected.

$\Rightarrow$ Suppose that $P = G \times H$ is connected.  We will
show that both $G$ and $H$ are connected.  Let $v_1$ and $v_2$ be
vertices in $G$, and let $w$ be an arbitrary vertex in $H$.  Since $P$
is connected, there is a path $p$ from $(v_1, w)$ to $(v_2, w)$.  Let
$p'$ be the subset of edges in $p$ of the first type.  By the
definition of the product graph, for each such edge:

\[
\{\ (v_i, w_k), (v_j, w_k)\ \}
\]

\noindent there is a corresponding edge in $G$:

\[
\{ v_i, v_j \}
\]

These edges define a path from $v_1$ to $v_2$ in $G$.  Thus, there is
a path between every pair of vertices in $G$, and so $G$ is connected.
A symmetric argument shows that $H$ is also connected.}

\end{problemparts}

\end{problem}

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

\begin{problem}
An $n$-cube is a graph whose vertices are $n$-bit strings.  There is
an edge between a pair of vertices if the corresponding strings differ
in a single bit position.  For example, here is a 3-cube:

\begin{center}
\includegraphics[height=1.25in]{ps3-3cube}
\end{center}

\begin{problemparts}

\problempart Use induction to prove that the number of edges in an
$n$-cube is $n 2^{n-1}$.

\solution{ 
\begin{proof}
The proof is induction on $n$.  Let $P(n)$ be the hypothesis that an
$n$-cube has $n 2^{n-1}$ edges.

As a base, $P(0)$ is true since there are no edges in a 0-cube (which
consists of a single vertex), and $0 2^{0 - 1} = 0$.  {\em (Note: One
could equally well use $P(1)$ as a base case, since no lower bound on
$n$ was specified.)}

In the inductive step, assume that an $n$-cube has $n 2^{n-1}$ edges.
The subgraph of a $(n+1)$-cube consisting of all vertices with a 0 in
the first bit position and the edges connecting them is isomorphic to
an $n$-cube.  By induction, this subgraph contains $n 2^{n-1}$ edges.
Similarly, the subgraph defined by all vertices with a 1 in the first
bit position is also isomorphic to an $n$-cube, and thus also has $n
2^{n-1}$ edges.  Furthermore, each vertex in an $(n+1)$-cube with a 0
in the first position is joined by an edge to a vertex with a 1 in the
first position.  There are $2^n$ such edges.  Thus, the total number
of edges in an $(n+1)$-cube is:

\begin{eqnarray*}
n \cdot 2^{n-1} + n \cdot 2^{n-1} + 2^n
	& = &	(n+1) 2^n
\end{eqnarray*}

The theorem follows by induction.
\end{proof}
}

\problempart Use induction to prove that an $n$-cube has a Hamiltonian
cycle for all $n \geq 2$.

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the hypothesis that
an n-cube has a Hamiltonian cycle.

For the base case, $P(2)$ is true, because a $2$-cube is itself a
cycle on four vertices.

For $n \geq 2$, suppose that an $n$-cube has a Hamiltonian cycle.
Then there is a Hamiltonian cycle on the subgraph of an $(n+1)$-cube
containing all vertices with first bit 0 and a corresponding
Hamiltonian cycle on the subgraph containing all vertices with first
bit 1.  We can merge these two cycles to obtain a Hamiltonian cycle on
the complete $(n+1)$-cube as follows.  Select an edge $\{u_0, v_0\}$
in the first cycle and the corresponding edge $\{u_1, v_1\}$ in the
second cycle.  Delete these two edges, and add the edges $\{v_0,
v_1\}$ and $\{u_1, u_0\}$.  This gives a Hamiltonian cycle consisting
of the portion of the first cycle from $u_0$ to $v_0$, the edge
$\{v_0, v_1\}$, the portion of the second cycle from $v_1$ to $u_1$,
and the edge $\{u_1, u_0\}$.

The theorem follows by induction.
\end{proof}
}

\problempart Use Kuratowski's Theorem to prove that a 4-cube is not a
planar graph.

\solution{The 4-cube contains a subgraph homeomorphic to $K_5$.  The
vertices are $0000$, $1000$, $0100$, $0010$, and $0001$.  There are
single edges between $0000$ and each of the other four vertices.
Between every other pair of vertices, there is a length-2 path that
goes through a vertex with two 1's.  For example, the path from 1000
to 0001 runs through vertex 1001.  No edge appears on two of these
length-2 paths, since the middle vertex on each path is distinct.}

\end{problemparts}
\end{problem}

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

\begin{problem}
The {\em complement} of a graph $G = (V, E)$ is a graph $\bar{G} = (V,
\bar{E})$.  The set $\overline{E}$ contains the edge $\{ u, v \}$ if
and only if that edge is not in $E$.  A graph $G$ is {\em
self-complementary} if $G$ and $\bar{G}$ are isomorphic.

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solution{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\begin{center}
\includegraphics[width=1.5in]{selfcomp}
%%\centerline{\resizebox{!}{1.5in}{\includegraphics{figures/selfcomp.eps}}}
\end{center}

}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solution{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is equivalent to either 0 or 1 modulo 4.

\solution{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}

\end{problem}

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

\begin{problem}
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.

\bigskip

{\bf Claim.} Every non-empty, tangled graph is connected.

\bigskip

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the proposition 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}

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

\problempart Draw a tangled graph that is not connected.

\solution{
\begin{figure}[htbp]
\centerline{\includegraphics[width=1.0in]{ps3-tangled-cx}}
\caption{Tangled but non-connected graph}
\end{figure}
}

\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 the following claim.

\bigskip

{\bf Claim.} Every non-empty, mangled graph is connected.

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

\end{problemparts}

\end{problem}




\end{document}                            
