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


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

%\hidesolutions
%\showsolutions

\begin{document}


\problemset{3}

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


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




\begin{problem}
A vertex $u$ is {\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 vertices in
undirected graphs.

\solution{

An equivalence relation is reflexive, symmetric, and transitive.  The
``connected to'' relation is reflexive since each vertex $v$ is
connected to itself because $v=v$.  It is symmetric since this is an
undirected graph and if $v_1$ is connected to $v_2$ then $v_2$ is
connected to $v_1$.  It is transitive since in an undirected graph, if
$v_1$ is connected to $v_2$ and $v_2$ is connected to $v_3$ then $v_1$
is (indirectly) connected to $v_3$.

}

\problempart What are the equivalence classes?
\solution{the connected components of the graphs}
\end{problemparts}
\end{problem}



\begin{problem}
Suppose the number of 6.042 recitations has been decreased to 8, but there are 2
TAs at each and the lecturers help out with several of the larger sections.

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

We want to determine a recitation schedule from this information.

\begin{problemparts}
\problempart Draw a graph representing this assignment of staff to recitations.
What do the vertices and edges represent?

\solution{
Need to fill in a graph drawing.

Each node represents a recitation section.  An edge connecting 2 vertices means
that there is a conflict (overlapping members) between the two committees.}

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

\solution{
The minimum coloring requires 4 colors:

\begin{itemize}
\item red=R1=R5\\
\item blue=R2=R7=R8\\
\item green=R4=R6\\
\item yellow=R3
\end{itemize}

4 meeting times, each represented with a different color.  Recitation sections
with the same color can meet concurrently.
}
\end{problemparts}
\end{problem}

\begin{problem}
An n-cube $Q_n$ has $2^n$ vertices represented as n-bit strings, and
an edge exists between a pair of vertices if the corresponding strings
differ in a single bit position.

Prove the following properties of n-cubes by induction:


\begin{problemparts}

\problempart  The number of edges for an n-cube ($n\geq1$) 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.

The base case $n=1$ is true since there is only one edge in a 1-cube
($1=1*2^0$).
In the inductive step, we assume that an n-cube has $n*2^{n-1}$ edges and
we consider strings of length n+1.  Those with last position $0$ form a copy of
$Q_n$, as do those with last position $1$.  So we have two copies of each of the
edges in $Q_n$.  We need edges connecting these two copies, and we
will need $2^n$ of those--one for each pair of strings of length $n+1$
varying in only the last position.  By the induction hypothesis, we need 
$2*(n*2^{n-1})+2^n=n*2^n+2^n=(n+1)*2^n$ edges for $n+1$-cube.
\end{proof}
}


\problempart  Every n-cube ($n\geq1$) has a Hamiltonian cycle.

\solution{

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

The base case P(1) is true since there is an edge between the only two vertices.
Now in the inductive step, we assume  $Q_n$ has a hamiltonian cycle for some
$n\geq1$ and we consider the strings of length  $n+1$.  Those with last 
position $0$ form a copy of $Q_n$, as do those with last position $1$.  To form a 
Hamiltonian cycle in $Q_{n+1}$, we take a cycle in the first copy, reverse it
in the second, and connect these two cycles.
\end{proof}
}

\problempart Use Kuratowski's Theorem to prove that $Q_4$ is not a planar graph.
\solution{There's a K3,3 in there.  I found it, but it will take a while to
draw out all the transformations I had to make.}

\end{problemparts}
\end{problem}




\begin{problem}


\textbf{Graphs}
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.

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


\end{problem}


\begin{problem}
A graph $G$ is {\em self-complementary} if $G$ and $\bar{G}$ are
isomorphic. $\bar{G}$ is the complement of $G$.  $\bar{G}$ has the same set
of vertices as $G$, but the edges in $\bar{G}$ are exactly those not present
in $G$.


\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 congruent to either 0 or 1 mod 4 (hint:
use part (b)).

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