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

\begin{problemparts}
\problempart Show that "connected to" is an equivalence relation on vertices.  



\solution{
reflexive:  each vertex can be considered connected to itself

symmetric:  if $v_1$ is connected to $v_2$ then $v_2$ is connected to $v_1$
since this is an undirected graph.

transitive:
Since this is 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}
Formulate some scheduling problem in terms of graph coloring, and then
    have them work out a small example.  (I'll do a problem like this in
    lecture.)

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:  KK, MT, Eric \\
\item R2:  KK, KP, Albert\\
\item R3:  MT, CL\\
\item R4:  EL, KP, Eric\\
\item R5:  EL, MW, Albert\\
\item R6:  MW, CL\\
\item R7:  MW, KP\\
\item R8:  MT, CL, Albert
\end{itemize}

How many different meeting times are needed with this arrangement?
Explain how you arrived at your answer.

\solution{
4 meeting times.
Each node represents a recitation section.  Connect 2 nodes if there is a 
conflict (overlapping members) between the two committees.
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}

}
\end{problem}

\begin{problem}
% http://www.math.gatech.edu/~trotter/Section4-EulerHam.htm

The n-cube  $Q_n$  consists of all  0-1  strings of length  n  with two strings adjacent when they differ in exactly one position.

% http://brakur.members.easyspace.com/cube/
An n-cube is a simple geometrical construct in an
R5-vectorspace, where every corner is a vector like (0,0,1,1,0) and
every two corners which differ in only one dimension (e.g. [0,0,0] and
[0,1,0]) are connected with a line. In two dimensions, this is a
square an in 3 dimensions it is the usual cube as we know it.

Prove the following properties of n-cubes by induction:


\begin{problemparts}


\problempart  The number of edges for an n-cube (n>1) is $2^n$.

\solution{ base case:  k=2 is true since squares have four edges.

Assume true for k.  Consider strings of length k+1.  Those with last
position 0 form a copy of $Q_k$, as do those with last position 1.  So
this is two copies of each of the edges in $Q_k$.  $2*2^k=2^{k+1}$

}


\problempart  Every n-cube (n>1) has a Hamiltonian cycle.

\solution{

%  http://www.math.gatech.edu/~trotter/Section4-EulerHam.htm
%  need to rewrite!
Proof.  True for n = 2.  Now assume  $Q_k$  is hamiltonian for some  k  > 1.   
Consider the strings of length  k + 1.  Those with last position  0  form a 
copy of $Q_k$, as do those with last position  1.  Take a cycle in the first 
copy and reverse it in the second [and connect them]

}
\end{problemparts}
\end{problem}


\begin{problem}
Let $G$ be a graph.  Prove that there is a path from every
vertex of odd degree to some other vertex of odd degree in $G$.

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

\end{problem}


\begin{problem}

 \textbf{Graph Coloring}

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

\solution{
  \begin{proof}
    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$. (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{proof}}

\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$ as defined in problem
6.

% The symbol $\bar{G}$, where $G$ is a graph, is defined in problem 33
% on page 456 of Rosen. The term ``isomorphic'' is defined on page 460
% of Rosen.

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





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

\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 Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n \cdot 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the Cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}
\end{problemparts}

\end{problem}


\end{document}                            
