\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\showsolutionstrue
\begin{document}
\solset{4}{March 8, 2001}

\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Velleman, \textit{How to Prove It}, everything you have not yet read
in Chapters~4 and~6.
Rosen, \textit{Discrete Mathematics and Its Applications}, Sections
6.5--6.6, 7.1--7.4, 7.8, and~8.1.


\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}
Rosen, \emph{Discrete Mathematics and Its Applications}, Section 1.6.

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.
\begin{enumerate}
\item Exercises from Rosen (answers in the back of the book): Section
  1.6, exercises 1, 7, 10, 11, 13, 15, 17.
\end{enumerate}
Note: the self-study problems are repeated from last week, since the
mini-quiz was replaced by the diagnostic test.


\medskip
\begin{problems} 

%%%%%%%%%%%EQUIVALENCE CLASS
%FALL 99
% problem set 4, problem 1
% equivalence classes

\problem \textbf{Equivalence Relations}
Let $(a,b) \sim (c,d)$ if $a+d = b+c$. We claim that $\sim$ is an
equivalence relation.

\begin{problemparts}

\problempart\points{4} Partition the set $\{0,1,2\} \times \{0,1,2\}$ 
into the distinct equivalence classes under $\sim$.

\solution{
We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ 
if $a-b = c -d$. This shows that with any equivalence class 
${\cal C}$ we can associate a {\em difference~$D$} such that 
$(a,b) \in {\cal C} \Rightarrow a - b = D$. This gives us an easy way to 
list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$.
\begin{itemize}
\item $D = -2$ : $\{(0,2)\}$.
\item $D = -1$ : $\{(0,1),(1,2)\}$.
\item $D = 0$  : $\{(0,0),(1,1),(2,2)\}$.
\item $D = 1$  : $\{(1,0),(2,1)\}$.
\item $D = 2$  : $\{(2,0)\}$.
\end{itemize}
}

\problempart\points{4}  Prove that $\sim$ is an equivalence 
relation on $\integers \times \integers$.

\solution{
\begin{itemize}
\item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$.
\item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ 
since $a + d = b + c \Rightarrow c + b = d + a$.
\item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. 
And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, 
i.e. $(a,b) \sim (e,f)$. 
Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$.
\end{itemize}
Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation.
}

\problempart\points{2} How many distinct equivalence classes under $\sim$ 
are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$? 
You do not need to prove your answer.

\solution{
$2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$.}
\end{problemparts}



%%%%%%%PARTIAL/TOTAL ORDER
\problem \textbf{Partial Orders}

\noindent In each case, say whether or not $R$ is a partial order on $A$.  If so, is it a total order?\\
a.\points{2} $A=\{a,b,c\}, R=\{(a,a),(b,a),(b,b),(b,c),(c,c)\}.$\\
b.\points{2} $A=\{$ the set of all words in English, $R = \{(x,y) \in A \times
A\  \mid \ $the word $x$ comes before the word $y$ alphabetically$\}$.\\
c.\points{2} $A=\reals, R=\{(x,y) \in \reals \times \reals \ \mid \ |x|\leq |y|\}$.\\
d.\points{2} $A=\reals, R=\{(x,y) \in \reals \times \reals \ \mid \ x \le y-3\}$.\\
e.\points{2} The relation ``is a parent of'' on people.


\solution{\textbf{Solutions:}\\
  a. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$
  is a partial order on $A$.  However, it is not a total order on~$A$
  since neither the pair $(a,c)$ nor $(c,a)$ is in $R$.\\
  b. $R$ is not reflexive (although it is transitive and antisymmetric),
  and thus it is not a partial order on~$A$.\\
  c. $R$ is reflexive and transitive. However, it is not antisymmetric.
  As a counterexample, $|-3| \leq |3|, |3| \leq |-3|$, but $3 \neq -3$. \\
  d. $R$ is not reflexive, and thus it is not a partial order on~$A$. \\
  e. The relation ``is a parent of'' is not reflexive, so it is not
     a partial order on people (a person is not a parent of himself).
     Note that this relation is not transitive or antisymmettic either.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% A new problem

\newcommand{\power}{\mathcal{P}}

\problem\textbf{Chains and antichains}

\noindent Let $A = \{1,2,\ldots,n\}$
and consider the partial order $(\power(A),\subseteq)$. (Remember that
$\power(A)$ is the set of all subsets of~$A$ and that $\subseteq$ is
the normal subset operator.)

\begin{problemparts}
  \ppart\points{5} Prove that there exists a chain of length~$n+1$ in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_0 = \emptyset$ and $A_i = A_{i-1} \cup \{i\}$ for
    $0 < i \leq n$. Then $A_i \subset A_{i+1}$ and there are $n+1$
    different $A_i$'s.}

  
  \ppart\points{5} Prove that for any integer~$k$ such that $0 < k < n$, the
  set $\{B \subseteq A : |B| = k\}$ is an antichain in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_k = \{B \subseteq A : |B| = k\}$ and consider
    $B_1,B_2 \in A_k$ such that $B_1 \neq B_2$. We prove the claim by
    contradiction, i.e., by assuming that $B_1$ and~$B_2$ are related.
    Thus, assume without loss of generality that $B_1 \subseteq B_2$.
    Since $B_1 \neq B_2$, this implies that $B_1 \subset B_2$, which
    implies that $|B_1| < |B_2|$, which contradicts the fact that
    $B_1,B_2 \in A_k$.  Thus $B_1$ and~$B_2$ are uncomparable, which
    implies that $A_k$~is an antichain.}
\end{problemparts}





% topic: graphs
% source: fall98 pset3 Problem 7

\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\points{3} 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]{figures/ps3-twographs}\end{center}


\solution{%
  \begin{samepage}
    \textbf{Solution:}
    \begin{center}
      \includegraphics[height=2in]{figures/ps3-product}
    \end{center}
  \end{samepage}
}

\problempart\points{7} 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}

\problem \textbf{Graphs --- Connectivity}
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\points{3} 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 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}

\solution{\textbf{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\points{2} Draw a tangled graph that is not connected.

\solution{%
  \begin{samepage}
    \textbf{Solution:}
    \begin{center}
      \includegraphics[height=1in]{figures/ps4-tangled-cx}
    \end{center}
  \end{samepage}
}

\problempart\points{5} 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 4, #7
\problem \textbf{Graph Coloring}\points{10}

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

\end{document}                            

