\documentclass[12pt]{article}
\input{macros-course}

%% Latex asks whether or not to include solutions
\askaboutsolutions
%\showsolutionstrue

\begin{document}

%% PSET 4: Partial Orders, Graphs (Rad, Fall01)
\ifshowsolutions
  \psetsol{4}{October 3, 2001}{\stamp}
\else
  \pset{4}{September 24, 2001}{extended to Oct. 3, beginning of lecture}{\stamp}
\fi

\ifshowsolutions
{} %
\else
\emph{You MUST include a \textbf{collaboration statement} and your
\textbf{TA's name} on the first page of your solutions.}
\fi

\textbf{Reading:} Rosen \S 6.6, Week 4 Lecture
Notes. \emph{Supplementary reading:} Velleman \S 4.4, Rosen \S 7.1-7.4,
7.8

%% Practice Problems: Partial / Total Orders
%% Velleman \s 4.4.1 good finger exercise, also recommend 4.4.5

\begin{problems}


%----------------------------------
% source: pRepository
% topic: posets
% last used: ??

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

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

\solnospace{
If $\alpha$, $\beta$ are strings, let us denote by
$\alpha\sqsubseteq\beta$ the fact that $\alpha$ is a \emph{prefix} of
$\beta$, i.e., that $\alpha\gamma=\beta$, for some $\gamma$.  Let us
also denote by $\alpha\restriction n$ the prefix of $\alpha$ of length
$n$. 

Then, the lexicographic order $R$ is such that 
$$
\alpha R \beta 
\:\iff\:
\alpha\sqsubseteq\beta 
\;\vee \;
\alpha\restriction t \prec \beta\restriction t
$$
where $t$ is the length of the shortest string. That is, $\alpha$ comes
before $\beta$ iff either it is a prefix of $\beta$ or its $t$-prefix
comes \emph{strictly} before the $t$-prefix of $\beta$ (in the
ordering of strings of length $t$, which we know is total). 

We first show that $R$ is a partial order. Reflexivity is obvious, and
antisymmetry is deduced easily: Suppose $\alpha R\beta$ and $\beta
R\alpha$. If any of the strings has its $t$-prefix strictly before the
$t$-prefix of the other string, then the latter one can't be a prefix
of the former; and it certainly cannot have its $t$-prefix strictly
before the $t$-prefix of the former string. Hence, the only
possibility is that both $\alpha \sqsubseteq \beta$ and
$\beta\sqsubseteq\alpha$, which implies $\alpha=\beta$.  

For transitivity, let's assume that $\alpha R\beta$ and 
$\beta R\gamma$, where $\alpha$, $\beta$, $\gamma$ are of 
length $m$, $n$, $l$, respectively, and $t=\min(m,n)$, 
$s=\min(n,l)$,  $r=\min(m,n,l)$. Then: 
\begin{itemize}
\item
If $\beta\sqsubseteq\gamma$, then $r=t$ and:
\begin{itemize}
\item If $\alpha\sqsubseteq\beta$, then $\alpha$ is also a prefix of
$\gamma$.
\item
If $\alpha\restriction t\prec\beta\restriction t$, then 
$\alpha\restriction r\prec\gamma\restriction r$, too.
\end{itemize} 
\item
If $\beta\restriction s\prec\gamma\restriction s$, then:
\begin{itemize}
\item
If $\alpha\sqsubseteq\beta$, then we either have
$\alpha\sqsubseteq\gamma$, or $\alpha\restriction
r\prec\gamma\restriction r$. 
\item
If $\alpha\restriction t\prec\beta\restriction t$, then we can infer
that again $\alpha\restriction r\prec\gamma\restriction r$.
\end{itemize}
\end{itemize}
Therefore, in any case, we have $\alpha R\gamma$; so $R$ is indeed
transitive, which concludes the proof $R$ is a partial order.

To prove that $R$ is total, consider any two $\alpha$, $\beta$ and
note that their $t$-prefixes are comparable (by the fact $\preceq$ over
strings of length $t$ is total). Equality of the prefixes implies one
of the strings is a prefix of the other; and any strict order of the
prefixes implies a similar order for the strings. In any case, the
strings are comparable. Which implies $R$ is total.
}


% OLD PROOF FOR PROBLEM 1
%Let $S$ be the totally ordered alphabet, $\preceq_S$ the total order
%on it, and $\prec_S$ the corresponding ``less than'' relation,
%$$
%a \prec_S b  
%\:\iff\: 
%a\preceq_S \wedge a\neq b,
%$$
%again on $S$. 
%
%In Rosen, $R$ is defined to be the relation that, for every two
%strings $\alpha,\beta\in S^\ast$, 
%$$
%\alpha R \beta  \:\iff\:  
%\alpha=\beta \;\vee\; \alpha\prec\beta,
%$$
%where $\prec$ is the following relation on $S^\ast$ (Rosen, p.~418): if
%$\alpha=a_1a_2\dots a_m$, $\beta=b_1b_2\dots b_n$, and $t=\min(m,n)$,
%then   
%$$
%\alpha\prec\beta
%\iff
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)
%\\
%\vee \bigl[
%	(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%	\wedge
%	m<n
%\bigr],
%$$
%$\prec_t$ being the lexicographic ordering that $\preceq_S$ induces
%onto $S^t$. 
%
%\medskip
%Let us first try to prove that $R$ is a partial order. One can easily
%verify that it is sufficient to show that $\prec$ is both
%assymetric\footnote{A relation $R$ on a set $A$ is assymetric iff, for
%all $x,y\in A$, $xRy\implies y\mbox{$\not\!\!R$}x$. Note that
%\emph{a}symmetry and \emph{anti}symmetry are different properties, in
%general. (See also Rosen Exercises~6.1.10--12.)} and transitive. So,
%we try to prove these two things.
%
%For assymetry, suppose $\alpha\prec\beta$, for arbitrary $\alpha =
%(a_1,a_2,\dots,a_m)$, $\beta  = (b_1,b_2,\dots,b_n)$. Then, setting
%$t=\min(m,n)$, we have either $(a_1,a_2,\dots,a_t) \prec_t
%(b_1,b_2,\dots,b_t)$, or $(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%\wedge m<n$. In the first case, there is an $i\in\{1,2,\dots,t\}$ such
%that  
%$$
%a_1=b_1,\quad  
%a_2=b_2,\quad  
%\dots,\quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i.
%$$
%This implies that certainly 
%$(b_1,b_2,\dots,b_t) \not\!\prec_t (a_1,a_2,\dots,a_t)$ and also that
%$(b_1,b_2,\dots,b_t) \neq (a_1,a_2,\dots,a_t)$; so,
%$\beta\not\prec\alpha$. In the second case, $\alpha$ is a proper
%prefix of $\beta$, which again easily implies that
%$\beta\not\prec\alpha$. 
%
%For transitivity, assume $\alpha\prec\beta$ and $\beta\prec\gamma$,
%for any  
%$\alpha = (a_1,a_2,\dots,a_m)$, 
%$\beta  = (b_1,b_2,\dots,b_n)$, and
%$\gamma = (c_1,c_2,\dots,c_l)$. Then, setting 
%$t=\min(m,n)$ and $u=\min(n,l)$, we have 
%$$
%\text{either } 
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t), 
%\text{ or }
%(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)\wedge m<n,
%$$
%and
%$$
%\text{either } 
%(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u), 
%\text{ or }
%(b_1,b_2,\dots,b_u) = (c_1,c_2,\dots,c_u)\wedge n<l,
%$$
%and we are left with four cases to examine. We study the most
%interesting one (the rest can be treated in similar ways), i.e., the
%case where both $(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)$, and  
%$(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u)$. Then we know there
%exist $i\in\{1,2,\dots,t\}$ and $j\in\{1,2,\dots,u\}$ such that 
%\begin{gather*}
%a_1=b_1,\quad 
%a_2=b_2,\quad  
%\dots,  \quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i,
%\\
%b_1=c_1,\quad  
%b_2=c_2,\quad  
%\dots,  \quad 
%b_{j-1}=c_{j-1},\quad  
%b_j\prec_S c_j.
%\end{gather*}
%Pick $k=\min(i,j)$. Then, we have 
%$$
%a_1=b_1=c_1,\quad  
%a_2=b_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=b_{k-1}=c_{k-1},\quad  
%a_k\preceq_S b_k \preceq_S c_k,
%$$
%where, in the last relation, at least one of the inequalities has to
%be strict ($\prec_S$, not $\preceq_S$), since $k$ has to equal at
%least one of $i,j$. Hence, what we really have is a
%$k\in\{1,2,\dots,\min(m,l)\}$ for which (also using the transitivity
%of $\prec_S$)
%$$
%a_1=c_1,\quad  
%a_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=c_{k-1},\quad  
%a_k\prec_S c_k;
%$$
%but this clearly implies that $\alpha\prec\gamma$.
%
%\medskip
%Finally, to prove that $R$ is total, consider two arbitrary strings
%$\alpha=(a_1,a_2,\dots,a_m)$, $\beta=(b_1,b_2,\dots,b_n)$, and again
%let $t=\min(m,n)$. If $\alpha=\beta$, then certainly $\alpha R\beta$,
%i.e., the strings are indeed comparable. If $\alpha$, $\beta$ are
%distinct, then there are two cases: either $a_i=b_i$ for all
%$i=1,2,\dots,t$, or there exists an $i\in\{1,2,\dots,t\}$ such that
%$a_i\neq b_i$. 
%
%In the first case it has to be $m\neq n$ (otherwise, we would have
%$\alpha=\beta$, which is false, by assumption); hence, either $m<n$,
%in which case $\alpha\prec\beta$, or $n<m$, in which case
%$\beta\prec\alpha$. (Notice our use of the fact that the natural
%ordering $\leq$ on the nonnegative integers is total.) So, $\alpha
%R\beta$ or $\beta R\alpha$, and the strings are comparable.
%
%In the second case, let $i_0$ be the least $i\in\{1,2,\dots,t\}$ for
%which $a_i\neq b_i$. Since the ordering $\preceq_S$ on $S$ is total,
%we know that either $a_{i_0}\prec_S b_{i_0}$ or $b_{i_0}\prec_S
%a_{i_0}$. Hence (also using the minimality of $i_0$), we have either
%$$
%a_1=b_1,\quad
%a_2=b_2,\quad
%\dots,  \quad
%a_{i_0-1}=b_{i_0-1},\quad  
%a_{i_0}\prec_S b_{i_0},
%$$
%in which case $\alpha\prec\beta$, or 
%$$
%b_1=a_1,\quad
%b_2=a_2,\quad
%\dots,  \quad
%b_{i_0-1}=a_{i_0-1},\quad  
%b_{i_0}\prec_S a_{i_0},
%$$
%in which case $\beta\prec\alpha$. So, again $\alpha R\beta$ or $\beta
%R\alpha$, and  the strings are comparable. 
%
%Therefore, in every case, $\alpha$ and $\beta$ are comparable; that
%is, $R$ is total.









\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering,
for alphabets with more than one element.

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

%%%%%%%%%%%%%%% GRAPHS:%%%%%%%%%%%%%%%%%

%-----------------------------------------------
% source: unknown, pRepository
% topics: adj matrices, chromatic number
% last used: ?

\problem The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
corresponds to row and column $i$ of the matrix.

\solnospace{ 
\begin{center}
\includegraphics[width=2in,height=2in]{figures/adjgraph}
\end{center}
%%\centerline{\resizebox{!}{2.0in}{\includegraphics{figures/adjgraph}}}
}

\problempart Give a coloring of the vertices that uses the minimum
number of colors. Prove that this a minimum coloring.

\solnospace{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}


%------------------------------------------------------------
% source: pRepository
% topic: general graphs

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

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

%-----------------------------------------------
% source: Rosen 7.8.21 (rewritten to be more clear)
% topics: coloring application (register coloring)
% last used: first time

\problem My computer program has seven variables, {\tt t,u,v,w,x,y,z},
and computes in 6 steps. The steps in which each variable is used are
as follows: {\tt t:} steps 1 through 6; {\tt u:} step 2; {\tt v:}
steps 2 through 4; {\tt w:} steps 1,3 and 5; {\tt x:} steps 1 and 6;
{\tt y:} steps 3 through 6; {\tt z:} steps 4 and 5. Each variable will
need to occupy the same index register at each one of the steps in
which it is going to be used; however during the steps when the
variable is not being used the register may be used by some other
variable. How many such registers are needed for my program? Explain
how you arrived at the answer.

\solnospace{This problem shows an application of graph coloring to
register allocation in a processor. Consider a simple graph $G$ having
the seven variables as its nodes, and an edge between two variables
iff there is at least one step of the program during which both
variables are going to be used.  Figure~\ref{fig:vars} contains the
graph we are talking about.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{figures/ps4-4a.latex}
\end{center}
\caption{}
\label{fig:vars}
\end{figure}

Clearly, two variables have to occupy different index registers iff
they are going to be used simultaneously sometime during the
progam execution, that is, iff they are connected in~$G$. 

To correctly and economically assign variables to registers means to
map each variable to one register in a way that does not cause
collisions (two simultaneously used variables mapped to the same
register) and uses as few registers as possible. But (if we think of
registers as colors) this is the same as to color $G$ in a way that
does not cause neighboring vertices of the same color and uses as few
colors as possible. So, we have reduced the original problem to the
problem of coloring~$G$.

Figure~\ref{fig:varscol} shows such a coloring, using 5 colors. To see
that this is the minimum one, just notice that variables $t$, $v$,
$w$, $y$, and $z$ form a 5-vertex subgraph which is complete, and
hence cannot be colored with less than~5 colors.

\begin{figure}
\begin{center}
\unitlength=0.035pt
\input{figures/ps4-4b.latex}
\end{center}
\caption{}
\label{fig:varscol}
\end{figure}

SIDE NOTE: In this problem we have assumed that a variable must always
use the same register, i.e. a variable is assigned a single
color. However in a real compiler this is overly restrictive because a
variable is backed up into memory every time it is evicted from the
register set and then reloaded from memory into the register set when
it needs to be used again. When it is reloaded there is no reason why
the same register must be used. For example, say we had a variable $x$
which is used in steps 1,2,3 and then later used in step 6. Then $x$
could be stored in register $r1$ for steps 1 through 3 and some other
register $r2$ for step 6. We can still use coloring to solve the
problem by treating $x$ as two separate variables: $x_{123}$ and
$x_6$. Since the number of variables in a computer program can be very
large and the register set of a processor is typically much smaller
(16-64 registers), register allocation is an important piece of
compiling.

}

%-----------------------------------------------
% source: Spring 95 Quiz 1, pRepository
% topics: graph connectivity

\problem The {\em complement} of an undirected graph $G=(V,E)$ is the
graph $\bar{G}=(V, \bar{E})$.  That is, $\bar{G}$ contains exactly
those edges that are not in $G$.  Prove that if $G$ is not connected
then $\bar{G}$ is.

\solnospace{
  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 $\bar{G}$.
\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 $\bar{E}$
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 $\bar{G}$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $\bar{G}$ is connected.
}

%-----------------------------------------------
% source: used by Albert in Fall 99, occasional tutorial
% topics: relations, adj matrices, paths, graphs

\problem Let $A$ be the adjacency matrix for a digraph $G$ with $n$
vertices.  Note that $A$ is a zero-one valued $n \times n$ matrix.  In
this problem we use the Boolean ``OR'' operation, $\vee$, instead of
``+'' when multiplying zero-one valued matrices (this is called
``boolean'' matrix product).

\problempart

For $k \geq 1$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

  \solnospace{%
    We prove this by induction on $k$.
%    Let $P(n)$ be the predicate that ${A^n}_{ij} = 1$ iff there is a
%    directed path of length $n$ from the $i$th to the $j$th vertex
%    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
%    on $n$.

    {\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix
    A, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$. We know,
    \[
	{A^{k+1}}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})
    \]

Now we consider both directions for the iff.


[$\Leftarrow$]
Suppose there is a directed path of length $k+1$ from the $i$th to the
$j$th vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  ${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,
\[
({A^k}_{il} \wedge A_{lj}) = 1
\]
which implies
\[
{A^{k+1}}_{ij} = 1.
\]

[$\Rightarrow$] 
Suppose that ${A^{k+1}}_{ij} = 1$. 
Then $\exists\; l \in V_G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}


\problempart Let $B = A \vee I$ where $I$ is the $n \times n$ identity
matrix.  Prove that ${B^k}_{ij} = 1$ iff there is a directed path of
length $\leq k$ from the $i$th to the $j$th vertex of $G$.

  \solnospace{%
    From part~(a), it can be seen that ${B^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since ${B^k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    ${B^k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.%
    }%
  

\problempart Conclude that ${B^n}_{ij} = 1$ iff there is a directed
path from the $i$th to the $j$th vertex.

\solnospace{
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$\leq n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $\leq n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $\leq n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}

\problempart If $A$ is the matrix for a relation $R$, show that $B^n$
is equal to the reflexive and transitive closure of $R$.

\solnospace{It is easy to see that the reflexive and transitive
closure of $R$ is $R^*\cup\Delta$, where $R^*$ is the connectivity
relation for $R$ (Rosen, p.~399--400), and $\Delta$ is the diagonal
relation on the set of vertices.

Now, to show that $B^n$ is the matrix of $R^*\cup\Delta$, it suffices
to show that 
$$
\text{for every two vertices $i$, $j$:} \quad
B^n_{ij} = 1 \iff (i,j)\in R^*\cup\Delta.
$$
The case where $i=j$ is easy: By definition of $\Delta$,
$(i,i)\in\Delta$, hence $(i,i)\in R^*\cup\Delta$; and, since there
exists a path (of length~0) from $i$ to $i$, $B^n_{ii}=1$,
by~(c). Therefore, the equivalence holds. 

For the case where $i\neq j$: If $B^n_{ij}=1$, then, by~(c), there is
a path from $i$ to $j$, which is of length at least~1 (because $i\neq
j$). Hence $(i,j)\in R^*$, so $(i,j)\in R^*\cup\Delta$,
too. Conversely, suppose $(i,j)\in R^*\cup\Delta$. Then, since $i\neq
j$, it has to be the case that $(i,j)\in R^*$, hence there exists a
path from $i$ to $j$. Which, by~(c), implies that $B^n_{ij}=1$.

Therefore, the equivalence holds in all cases, which implies $B^n$ is
indeed the matrix of $R^*\cup\Delta$.
}

%-----------------------------------------------
% source: Rosen ??
% topics: isomorphism

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

\solnospace{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]{figures/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.

\solnospace{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)).

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

%-----------------------------------------------
% source: Rosen 7.3.45
% topics: isomorphism
% last sued: first time
% \problem {\bf EITHER (Isomorphism)} Rosen 7.3.45, Show that
% isomorphism on is an euivalence relation on graphs.



%-----------------------------------------------
% source: pRepository
% topics: graph connectivity

% \problem An edge of a connected graph is called a {\em cut-edge} if
% removing the edge disconnects the graph.  Prove that an edge $e$ in a
% connected graph $G$ is a cut-edge if and only if no simple cycle
% contains $e$.

% %% NOTE: already corrected in lecture notes s99, states that no edge
% %% is to be repeated (RAD)
% % For this problem, use the definition of a ``simple cycle'' given on
% % page 468 of Rosen (p.463 in ed.3).  (The lecture notes require a
% % simple cycle to have no repeated vertex, but Rosen requires no
% % repeated edge.)

% \solnospace{
% \begin{proof}
% First, we prove that if $e$ is contained in a simple cycle, then $e$
% is not a cut-edge.  Since $G$ is connected, there exists a path $P$
% between every pair of distinct vertices $u$ and $v$.  We must show
% that there still exists a path between $u$ and $v$ after edge $e$ is
% removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
% cycle containing $e$.  Since the cycle is simple, none of the edges
% $e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
% a new path that connects $u$ and $v$, but does not contain edge $e$ by
% substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
% e_1$ in place of edge $e$ in the path $P$.  (Which sequence is
% substituted for edge $e$ depends on the direction in which the path
% $P$ traverses the edge $e$.)  This shows that the graph remains
% connected after edge $e$ is removed, and so edge $e$ is not a
% cut-edge.

% Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
% a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen,
% which states that there is a {\em simple} path between every pair of
% distinct vertices in a connected graph.  Since $e$ is not a cut-edge,
% the graph obtained by removing edge $e$ is connected.  So by the
% theorem, there exists a simple path $P$ connecting the endpoints of
% edge edge $e$ even after edge $e$ is removed from the graph.
% Adjoining edge $e$ to path $P$ gives a simple cycle containing edge
% $e$.
% \end{proof}
% }

\end{problems}

\end{document}                            
