\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

\newcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\kth}{\ensuremath{^\mathit{\textit{\tiny th}}}}

\begin{document}
\pset{4}{September 30, 1999}{start of tutorial, October 8, 1999}

\textbf{Reading} The Rosen text, \S 6 S99 Handout 12 pp16--18;
\S 7.1--4, 7.8; S99 Handout 12 sec 1--4

{\large
Remember to include a \textbf{collaboration statement} on the front page
of your solutions (see Handout 2, \emph{Course Information}).}

Note: None of these problems requires a lot of writing.  Consider this
when writing up your solutions.

\begin{problems}

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

\problem \textbf{Posets}

Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

\begin{problemparts}

\problempart Prove that $R$ is a total order.

\solution{We first show that $R$ is a partial order.
Reflexivity is clear from the definition. To show antisymmetry,
suppose that $a_1\ldots a_m<b_1\ldots b_n$, and let $t=\min(m,n)$. This
means that either $a_1\ldots a_t = b_1\ldots b_t$ and $m<n$, so that
$b_1\ldots b_n \not <a_1\ldots a_m$, or else $a_1\ldots a_t<b_1\ldots b_t$,
so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again 
$b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that
$a_1\ldots a_m<b_1\ldots b_n<c_1\ldots c_p$
. Let $t=\min(m,n)$, $r=\min(n,p)$,
$s=\min(m,p)$, and $l=\min(m,n,p)$. Now if 
$a_1\ldots a_l<b_1\ldots b_l<c_1\ldots c_l$
then clearly $a_1\ldots a_m<c_1\ldots c_p$. Otherwise, without loss
of generality we may assume that $a_1\ldots a_l=b_1\ldots b_l$. If $l=t$
then $m<n$ and $m\le p$. Furthermore, either $b_1\ldots b_r<c_1\ldots c_r$
or $b_1\ldots b_r=c_1\ldots c_r$ and $n<p$. In the former case, if 
$r>l$, then since $p>m$ we have $a_1\ldots a_m<c_1\ldots c_p$, whereas if 
$r=l$ then $a_1\ldots a_l<c_1\ldots c_l$. In the latter case, 
$a_1\ldots a_s=c_1\ldots c_s$ and $m<p$, so again 
$a_1\ldots a_m<c_1\ldots c_p$. If $l<t$, then we must have 
$b_1\ldots b_l<c_1\ldots c_l$, whence $a_1\ldots a_l<c_1\ldots c_l$.
Finally, the fact that $R$ is a total order follows trivially from the 
definition of a lexicographic order and noticing
that the strings of symbols are taken from a totally ordered alphabet.
}

\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering.

\solution{
Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$ is not
a well ordering since $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no least element.
Moreover, $R^{-1}$ is not a well-ordering since $\{a,aa,aaa,aaaa,\ldots\}$
has no least element. 
%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}

\end{problemparts}

\problem \textbf{Edges and Vertices}

Do \S 7.2, Exercise 26 (part a) from the Rosen textbook.

\solution{
We want to show that $2 e\ge v m$. We know from Theorem 1 (Rosen)
that $2 e$ is the sum of the degrees of the vertices. This certainly cannot 
be less than the sum of $m$ for each vertex, since each degree is no less
than $m$.
}

\problem \textbf{Bipartite Graphs}

Do \S 7.2, Exercise 36 from the Rosen textbook.

\solution{
Suppose the parts are of size $k$ and $v-k$. Then the maximum number of
edges the graph may have is $k(v-k)$ (an edge between each pair of 
vertices in different parts). By algebra of calculus, we know that the 
function $f(k)=k(v-k)$ schieves its maximum when $k=v/2$, giving 
$f(k)=v^2/4$. Thus there are at most $v^2/4$ edges.
}

\problem \textbf{Isomorphism}

\begin{problemparts}

\problempart Do \S 7.3, Exercise 36 from the Rosen textbook.

\solution{
These graphs are not isomorphic. The second has a vertex of degree 4,
whereas the first does not.
}

\problempart Do \S 7.3, Exercise 38 from the Rosen textbook.

\solution{
These two graphs are isomorphic. Each consists of a $K_4$ with a fifth vertex
adjacent to two of the vertices in the $K_4$. Many isomorphisms are possible.
One is $f(u_1)=v_1$, $f(u_2)=v_3$, $f(u_3)=v_2$, $f(u_4)=v_5$, and 
$f(u_5)=v_4$.
}

\end{problemparts}

\problem \textbf{Connectivity}

% Spring 95 Quiz 1
The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 
Prove that if $G$ is not connected then $G^c$ is.

\solution{
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $G^c$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $E^c$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $G^c$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $G^c$ is connected.
}

\problem \textbf{Graph Coloring}

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

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

\end{document}








