\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
%\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}



%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

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

\begin{document}

\handout{tut4}{Mini-Quiz 4}{March 2, 2001}
\begin{enumerate}
\item Your name:
\item Determine whether each of the following functions from $\mathbb{Z}$ to $\mathbb{Z}$ is \begin{enumerate}
\item one-to-one
\item onto
\end{enumerate}(mark box with X if yes, leave blank if no)
\end{enumerate}
\begin{table}[h]
\begin{tabular}{|c|c|c|}
\hline
Function&One-to-One?&Onto?\\ \hline
$f(n)=n-1$&&\\ \hline
$f(n)=n^2+1$&&\\ \hline
$f(n)=n^3$&&\\ \hline
$f(n)=\lceil\frac{n}{2}\rceil$&&\\ \hline
\end{tabular}
\end{table}


\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage



\handout{tut4}{Tutorial 4 Problems}{March 2, 2001}


\begin{problems}
               
          
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{2.0in}{\includegraphics{figures/dag.eps}}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

\problempart What's the length of a critical path; find such a path.

\solution{
\medskip
\textbf{Solution:}\\
The sequence 18.01, 18.03, 6.002, 6.004, 6.033, 6.857 constitutes
a critical path since it is the longest directed path in the graph.}

\problempart How many terms are necessary and sufficient to complete
all of the courses in Figure~\ref{fig:dag}, assuming prerequisites are
observed, but course load is no issue? Prove your answer (both
necessary and sufficient).

\solution{
\medskip
\textbf{Solution:}\\
The answer is suggested by the way Figure~\ref{fig:dag} is drawn---each
horizontal row is an antichain.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms. Furthermore, since there is a critical path of length six,
there is no way to finish in less than six terms.}

%\problempart Show that there is a schedule for taking courses
%which achieves the minimum number of terms, $t$.  
%the previous question includes this direction

%\solution{
%\medskip
%\textbf{Solution:}\\
%    The solution to the previous part implies that $t$ terms are
%    sufficient.  In term $i$, the student should take the set of
%    courses in the $i$th block.  Since the edges into any block come
%    from an earlier block, all the prerequisites of courses in a block
%    have been taken by the time the block is scheduled to be taken.
%    And since the blocks partition the set of all courses, the student
%    will complete every course.
%  }        


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem %
Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends.

\bparts
\ppart

Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.  \hint See part (d).

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\solution{
\medskip
\textbf{Solution:}\\
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\ppart
Explain briefly, but clearly, what is wrong with the following
argument:

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n~\ge~1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.


\solution{
\medskip
\textbf{Solution:}\\

The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).  

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.

   }


\ppart
Here is another argument for the same False Theorem as in part~(b).
Explain exactly where it goes wrong.

\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.

\solution{
\medskip
\textbf{Solution:}\\
The claim
\begin{quotation}\noindent
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.
\end{quotation}
is wrong.  The degree of $w$ is one less
in~$G_n$ than it was in~$G_{n+1}$, hence it can be equal to one if it
was two in $G_{n+1}$, but it can also be equal to zero if it was one
in $G_{n+1}$.  The false proof above is wrong because it ignores this
this second possibility.  For example, if we take $G_{n+1}=G_4$ from
the solution to part (a):\\
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(00,20){w}
\put(20,20){v}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}}
\put(00,20){w}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not a line graph.}


\ppart
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\solution{
\medskip
\textbf{Solution:}\\
The proof in part (c) can be easily fixed if the graphs are connected,
because then the quoted false claim will be true.  Here is an
example of how one could inject into the proof from part (c) an
argument justifying the claim for the case of connected
graphs:
\begin{quotation}
[...But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$.]
Since $G_{n+1}$ was two-ended, $w$ must be of degree either one or two
in $G_{n+1}$.  However, it cannot be of degree one because then
vertices $v$ and $w$ would be connected only to each other and
disconnected from the rest of the graph, which would contradict the
assumption that $G_{n+1}$ is connected.  Therefore, $w$ must have
degree two in $G_{n+1}$, and hence has degree one in $G_n$.
Hence, [ $G_n$ still has two vertices of degree~one and one fewer
vertex of degree~two.  Therefore...]
\end{quotation}

The false proof in part (b) cannot be easily fixed.  If we tried to
use its structure to prove that all connected two-ended graphs are
linear graphs, we would have to supply the argument that every
connected two-ended graph can be formed by adding an edge to some
connected two-ended graph with one less edge.  To argue that would be
as complicated as the above proof.
 
  }  \eparts
        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\renewcommand{\labelenumi}{\alph{enumi})}
 
%from fall00
\problem \textbf{Well-ordering}
 
%\textbf{Rosen 3.2, Ex. 58:} 
The well-ordering property can be used to show that there is a unique
greatest common divisor of two positive integers. Let $a$ and $b$
be positive integers, and let $S$ be the set of positive integers of the
form $as+bt$, where $s$ and $t$ are integers.
\begin{enumerate} \setlength{\itemsep}{0pt} \item Show that $S$ is nonempty.
\item Use the well-ordering property to show that $S$ has a smallest
  element $c$.
\item Show that if $d$ is a common divisor of $a$ and $b$, then $d$ is
  a divisor of $c$.
\item Show that $c \mid a$ and $c \mid b$. (Hint: First, assume that
  $c \nmid a$.  Then $a=qc+r$, where $0<r<c$. Show that $r \in S$,
  contradicting the choice of $c$.)
\item Conclude from (c) and (d) that the greatest common divisor of
  $a$ and $b$ exists. Finish the proof by showing that this greatest
  common divisor of two positive integers is unique.
\end{enumerate}

\renewcommand{\labelenumi}{\alph{enumi})}
\solution{
\medskip
\textbf{Solutions:}\\

\begin{enumerate} \setlength{\itemsep}{0pt}
\item For example, just set $s=1$, and $t=1$.  Then $as+bt = a+b$,
  which is a positive integer by our definitions of $a$ and $b$.
\item The Well Ordering Property states that every non-empty set of
  non-negative integers has a smallest member.  Since we just showed
  in part a that the set $S$ is non-empty, it must have a smallest
  member, which we may call $c$.
\item If $d$ divides $a$ and $b$, then $d$ divides $as$ and $bt$ for
  any positive integers $a$ and $b$.  Therefore, $d$ also divides the
  sum $as+bt$.  Since $c \in S$, c must be such a sum, by our
  definition of membership in $S$.  Therefore, $d$ can divide $c$.
  
  
\item We will just show $c \mid a$, as the argument is identical to
  show $c \mid b$.\\
  Proof by Contradiction.\\
  Assume for the purpose of contradiction that $c \nmid a$.\\
  If $c$ does not evenly divide into $a$, then we can write the expression $a = qc + r$, for some postive integer $r$, where $0<r<c$.\\
  We can rewrite this in terms of $r$: $r=a-qc$.\\
  Now, since $c \in S$, we know that $c$ is of the form $c=as+bt$, for some integral values of $s$ and $t$.  Rewriting our expression for $r$ again, we get:\\
  $r=a-qc = a-q(as+bt)=a-aqs-qbt=a(1-qs)+b(-qt).$ But now we are done,
  because we have expressed the positive integer $r$ as a linear
  combination with integer coefficients of $a$ and $b$.  This means
  that $r \in S$, which we know is not possible since $r<c$.  Thus, we
  have a contradiction, and our assumption that $c \nmid a$
  must be wrong, so we can conclude that $c \mid a$.
  
\item Finally, by part (d), $c$ is a divisor of both $a$ and $b$.
  Furthermore, from part (c) we know that any divisor of both $a$ and
  $b$ is also a divisor of $c$.  This means that every common divisor
  of $a$ and $b$ is no greater than $c$, and so $c$ is the greatest
  common divisor of $a$ and $b$.  To see that the greatest common
  divisor of a number is unique, one just needs to note that it makes
  no sense to have two numbers, each of which is greater than the
  other.
\end{enumerate}
}                                  






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%this problem appeared in a problem set in fall 00
%very few people who didn't go to office hours got it right, even though
%it's not particularly difficult. Perhaps doing it in tutorial is a better idea


\problem \textbf{Dilworth}

At last count, our 6.042 class contains 180 students.
Prove that the class must contain either: \begin{enumerate} \setlength{\itemsep}{0pt} %\setlength{\itemsep}{0cm}
\item A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
\item a set $T$ of 13 students such that, if they line up in size
places, they are also arranged in decreasing order of age.  \end{enumerate}
To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in increasing order, but not in strictly increasing order.



\solution{
\medskip
\textbf{Solution:}\\
For each student, we can assign a pair $(s,a)$ where $s$ represents the size (height) of the student and $a$ represents the age of the student. We then get a set $U$ of 180 such pairs. We can define the following binary relation $R$, denoted by $\preceq$, between two pairs $P_{1}$ and $P_{2}$: 
$P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and $a_{1}\leq a_{2}$. 

For example, if $P_{1}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185, 19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are incomparable.

It is easy to check that $R$ is reflexive, transitive and antisymmetric. Thus, it defines a partial order on the set $U$. By Dilworth's Theorem, since $U$ has 180 elements, it must either have a chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$. 
\subparagraph{Case 1} $U$ has a chain of size $> 14$. Then it has a chain of size at least 15. This means that we can find 15 pairs which satisfy the relation $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the definition of our binary relation $(\preceq)$, this implies that $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the corresponding 15 students in the same order, they will be lined up in in increasing order of size AND in increasing order of age.

\subparagraph{Case 2} $U$ has an antichain of size $\geq\frac{180}{14}$, so, since antichains only come in integer lengths, it has an antichain of size at least 13. Therefore, we can find 13 pairs which are incomparable. We can line them up in order of increasing size (ignoring age), and  come up with an order $P_{1}\ldots  P_{13}$ so that $s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that $a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$, $s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we take the students corresponding to $P_{1}\ldots  P_{13}$ and line them up in that order, they will be in increasing order of size (since $s_{i}\leq s_{i+1}$) and in decreasing order of age (since we established that $a_{i}>a_{i+1}$).



}


\end{problems}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations}


Consider the following putative theorem and the accompanying proof.
\begin{theorem*}
  For any sets $A$, $B$, $C$, and $D$, if $A \times B \subseteq C
  \times D$ then $A \subseteq C$ and $B \subseteq D$.
\end{theorem*}
\begin{proof}
  Suppose $A \times B \subseteq C \times D$.  Let $a$ be an arbitrary
  element of $A$, $b$ be an arbitrary element of $B$, and $(a, b) \in
  A \times B$.  Since $A \times B \subseteq C \times D$, it follows
  that $(a, b) \in C \times D$.  Therefore, $a \in C$ and $b \in D$.
  Since $a$ and $b$ were arbitrary elements of $A$ and $B$,
  respectively, this shows that $A \subseteq C$ and $B \subseteq D$.
\end{proof}
Is the proof correct?  If so, what proof strategies does it use?  If
not, can it be fi xed?  Is the theorem correct?

\solution{
\medskip
\textbf{Solution:}\\
    The problem lies in the statement \emph{``let $a$ be an arbitrary
      element of $A$''} (and without loss of generality, $b$ an
    arbitrary element in $B$).  Namely, if $A = \emptyset$, $B = \{1,
    2, 3\}$, $C = \{1, 2\}$, and $D = \{3, 4\}$, then $A \times B
    \subseteq C \times D$ ($\emptyset \subseteq E$ for any set $E$),
    but $B \not\subseteq D$.  This is an example of the proof failing
    at a boundary case.
  }

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



\problem \textbf{Relations and Matrices} 

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

%\begin{problemparts}

\problempart

For $k \in \naturals$, 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$.

%\omitsolution{%
  \solution{%
    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)$.
 
\[{A^k}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})\]

Now we consider both directions for the iff.

Case 1:

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\]
\[{A^{k+1}}_{ij} = 1\]

Case 2: ${A^{k+1}}_{ij} = 1$.

Then $\exists\; l \in 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$.

%\omitsolution{%
  \solution{%
    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.

%\omitsolution{%
\solution{
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
$<=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 $<=n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $<=n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}
                        


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





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



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


\end{problems}
\end{document} 
