\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

\begin{document}
\lecturenotes{4}{Graphs}

\section{Graph Definitions}

{\em Graphs} are mathematical objects used heavily in Computer
Science.  Often one can reduce a real-world problem to a purely
mathematical statement about graphs.  If the graph problem can be
solved, then --- in principle at least --- the real-world problem is
solved. Already we've seen examples of using graphs to represent
relations (which in turn model real world problems). Graphs give a
picture of the relation, which is often much more revealing than a
list of tuples.

A nuisance in first learning graph theory is that there are so many
definitions.  They all correspond to intuitive ideas, but can take a while
to absorb.  Worse, the same thing often has several names and can even
have several equivalent definitions!

\subsection{Simple Graphs}

A {\em simple graph} is a pair of sets $(V, E)$.  Elements of $V$ are
called {\em vertices}.  An element of $E$ is called an {\em edge}.  The
basic property of an edge in a simple graph is that it adjoins two
vertices.  Formally, we identify an edge with the two vertices it adjoins.
That is, the elements of $E$ are specified to be subsets of $V$ of size
two.

Graphs are also sometimes called {\em networks}.  Vertices are also
sometimes called {\em nodes}.  Edges are sometimes called {\em arcs}.  If
$u \neq v$ are vertices of a simple graph and the set $\set{u, v}$ is an
edge of the graph, this edge is said to be {\em incident} to $u$ and $v$.
Equivalently, $u$ and $v$ are said to be {\em adjacent} or {\em
neighbors}.  Phrases like, ``an edge joins $u$ and $v$'' and ``the edge
between $u$ and $v$'' are common. Notice that a simple graph in fact
represents a {\em symmetric} relation, any two vertices, $u$ and $v$, that
are connected by an edge are related to each other in both directions
($uRv$ and $vRu$).  Simple graphs are also sometimes called
\emph{undirected} graphs.

Graphs can be nicely represented with a diagram of dots for vertices and
lines for edges as shown in Figure~\ref{fig:graph}.

\begin{figure}[htbp]
\centering \includegraphics[height=2in]{figures/graph}
%\centerline{\psfig{figure=figures/graph.eps,height=2in}}
\caption{\em This is a picture of a graph $G = (V, E)$.  There are 4
vertices and 4 edges.  The set of vertices $V$ is $\{1, 2, 3, 4\}$.  The
set, $E$, of edges is $\set{\set{1,2}, \set{1,3}, \set{2,3}, \set{3,4}}$.
Vertex 1 is adjacent to vertex 2, but is not adjacent to vertex 4.}
\label{fig:graph}
\end{figure}

\subsection{Not Simple Graphs}

Simple graphs are just one kind of graph; there are other kinds, often not
as simple.

\subsubsection*{Multigraphs}

In a simple graph, there are either zero or one edges joining a pair of
vertices.  In a {\em multigraph}, multiple edges are permitted between the
same pair of vertices.\footnote{This requires that an edge be represented
as something slightly more than just two endpoints, for example
as an ordered pair whose first element is a number and whose second
element is the two endpoints.}  There may also be edges called {\em
self-loops} that connect a vertex to itself.  Figure~\ref{fig:multigraph}
depicts a multigraph with self-loops.

\begin{figure}[htbp]
\centering \includegraphics[height=1.5in]{figures/multigraph}
% \centerline{\psfig{figure=figures/multigraph.eps,height=1.5in}}
\caption{\em This is a picture of a multigraph with a self-loop.  In
particular, there are three edges connecting vertices 1 and 2 and there
is a self-loop on vertex 3.}
\label{fig:multigraph}
\end{figure}

\subsubsection*{Directed Graphs}

Like a simple graph, a {\em directed graph} or {\em digraph} is a pair
of sets $(V, E)$ where $V$ is a set whose elements are called
vertices.  Now the edges are regarded not as lines, but as arrows
going from a \emph{start} (or \emph{tail}) vertex to an \emph{end} (or
\emph{head}) vertex.  Formally, an edge in $E$ is specified to be an
ordered pair of vertices.  In other words, $E \subseteq V\times V$,
where $V \times V$, the Cartesian product of $V$ with itself, is the
set of all ordered pairs of elements of $V$. Notice that the
definition of $E$ is the same as that of a relation on the set $V$, so
in fact a directed graph can be used to model any relation on a
set. Figure~\ref{fig:digraph} depicts a directed graph.

\begin{figure}[htbp]
\centering \includegraphics[height=1.5in]{figures/digraph}
% \centerline{\psfig{figure=figures/digraph.eps,height=1.5in}}
\caption{\em This is a picture of a directed graph or digraph.}
\label{fig:digraph}
\end{figure}

\subsubsection*{Weighted Graphs}

Sometimes it is useful to associate a number, often called its
\emph{weight}, with each edge in a graph.  Such graphs are called
\emph{edge-weighted} or simply \emph{weighted} graphs; they may be simple,
directed, multi, etc.  The weight of an edge $(u, v)$ of a digraph is
often denoted $w(u, v)$.  More generally, edges (or nodes) may be labelled
with elements from some designated set of labels --- these are called edge
(or node) \emph{labelled} digraphs, simple graphs, multigraphs, etc.

\section{Graphs in the Real World}

There are many real-world phenomena that can be described nicely by
graphs.  Here are some examples:

\begin{description}

\item[Computer network] The set of vertices $V$ represents the set of
computers in the network.  There is an edge $(u, v)$ iff there is a direct
communication link between the computers corresponding to $u$ and $v$.

\item[Airline Connections] Here the vertices are airports and edges are
flight paths.  We could indicate the direction that planes fly along each
flight path by using a directed graph.  We could use weights to convey
even more information.  For example, $w(i, j)$ might be the distance
between airports $i$ and $j$, or the flying time between them, or even the
air fare.  The edges might also be labelled with the set of call signs
(\texttt{TW}, \texttt{AA}, \dots) of airlines using that flight path.

\item[Precedence Constraints] Suppose you have a set of jobs to
complete, but some must be completed before others are begun.  (For
example, Atilla advises you always pillage {\em before} you burn.)
Here the vertices are jobs to be done.  Directed edges indicate
constraints; there is a directed edge from job $u$ to job $v$ if job
$u$ must be done before job $v$ is begun.

\item[Program Flowchart] Each vertex represents a step of computation.
Directed edges between vertices indicate control flow.

\item[Two-Player Game Tree] All of the possibilities in a board game like
chess can be represented in a graph.  Each vertex stands for one possible
board position.  (For chess, this is a very big graph!)

\end{description}


 \iffalse
 An example is
 shown in Figure~\ref{fig:game}.


 \begin{figure}[htbp]
 \centerline{\psfig{figure=figures/game.eps,height=2.0in}}
 \caption{\em This is a picture of a game tree.  The topmost vertex
 represents the starting position.  The edges descending from this
 vertex represent possible moves by the first player.  The second tier
 vertices represent board positions after one move, and the edges below
 represent possible moves by the second player.  A complete game can be
 represented by a path from the top vertex to a ``leaf'' vertex at the
 bottom of the diagram.}
 \label{fig:game}
 \end{figure}
 \fi

Some graphs appear so frequently that they have names.  The most important
examples are shown in Figure~\ref{fig:zoo}.

\begin{figure}[htbp]
\centering \includegraphics[height=3in]{figures/zoo}
% \centerline{\psfig{figure=figures/zoo.eps,height=3.0in}}
\caption{\em The types of graph shown here are so common that they have
names.  (a) The \emph{empty graph} or \emph{\underline{A}nticlique} on five vertices, $A_5$.
An empty graph has no edges at all.  (b) The \emph{cycle} on five vertices,
$C_5$.  (c) The \emph{complete graph} on five vertices, $K_5$.  A complete graph
has an edge between every pair of vertices.  (d) A five-vertex \emph{line graph}.
(e) A $5 \times 5$ \emph{2-dimensional mesh}.}
\label{fig:zoo}
\end{figure}

\section{Graph Isomorphism}
Graphs are intended to be abstract data types.  This means what matters
about a graph is only its connectedness: which vertices are incident to
which edges, but not what the vertices actually are.  For example the
simple graph whose vertices are the integers $1,\dots,2n$ with an edge
between two vertices iff they have the same parity (that is, both are even
or both are odd), has the same connectedness as the graph whose vertices
are $-1,-2,\dots,-2n$ with an edge between two vertices iff either both
vertices are $< -n$ or both are $\geq -n$, since in each case, the graph
has two disjoint sets of $n$ vertices, with all possible edges between
vertices in the same set and none between a vertex and any of the vertices
in the opposite set.  Technically we say the graphs are \emph{isomorphic}
when their vertices can be put in exact correspondence so that an edge
between two vertices in one graph corresponds exactly to an edge between
corresponding vertices in the other graph.

It helps to say this in precise mathematical style.
Namely, digraphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic iff
there is a bijection $f:V_1 \to V_2$ such that for all $u,v \in V_1$
\[(u,v) \in E_1 \iff (f(u),f(v)) \in E_2.\]
The bijection, $f$, is called an \emph{isomorphism} between the graphs.
For example, the function $f: \set{-1,\dots,-2n} \to \set{1,\dots, 2n}$,
where $f(k) = -2k$ if $-n \leq k \leq -1$ and $f(k) = 2(2n + k) + 1$ if
$-2n \leq k < -n$, is an isomorphism between the two graphs described
above.

\section{Properties of Graphs}

When one is confronted by a new graph --- say in a dark alley --- there is
often a need to study properties at a higher-level than, ``Is vertex $u$
connected to vertex $v$?''  Some questions that might arise are, ``How
many edges are incident to each vertex?'', ``Is the graph all in one piece
or in several pieces?'', ``How can we color the vertices?''  (The last may
seem odd, but comes up surprisingly often; we'll see why in a minute.)
This section discusses some of these higher-level properties of graphs.

\subsection{Vertex Degree}

The {\em degree} of a vertex is the number of edges incident to it.  The
degree of vertex $v$ is often denoted $d(v)$.  In a digraph, we might also
examine the \emph{in-degree} (resp. \emph{out-degree}) of a vertex, namely
the number of edges into (resp. out of) a vertex.

For example, referring to Figure~\ref{fig:zoo}, every vertex in an empty
graph has degree 0, but every vertex in a cycle has degree 2.  A simple
example of what we mean by a ``higher-level'' property of simple graphs
is:

\begin{theorem}\label{sumedges}
The sum of the degrees of the vertices in a simple graph equals twice the
number of edges.
\end{theorem}

\begin{proof}
Every edge contributes two to the sum of the degrees, one for each of its
endpoints.
\end{proof}

\begin{problem*}
\bparts
\ppart The previous proof is not as precise as we desire
at the beginning of 6.042.  Rewrite the proof more carefully as an
induction on the number of edges in a simple graph.
\ppart  Extend Theorem~\ref{sumedges} to multigraphs.

\ppart Extend Theorem~\ref{sumedges} to digraphs.
\eparts
\end{problem*}

Here is a puzzle that can be addressed with graphs.  There is a party.
Some people shake hands an even number of times and some shake an odd
number of times.  Show that an even number of people shake hands an
odd number of times.

We can represent the party by a graph.  (Yeah, right.)  Each person is
represented by a vertex.  If two people shake hands, then there is an
edge between the corresponding vertices.  This reduces the problem to
the following theorem:

\begin{theorem}
In every graph, there are an even number of vertices of odd degree.
\end{theorem}

\begin{proof}
Partitioning the vertices into those of even degree and those of odd
degree, we know
\[
{\sum_{v \in V} d(v)}\ =
{{\sum_{d(v) \mbox{ {\scriptsize is odd}}} d(v)}\ +\
{\sum_{d(v) \mbox{ {\scriptsize is even}}} d(v)}}
\]
The value of the lefthand side of this equation is even, and the second
summand on the righthand side is even since it is entirely a sum of even
values.  So the first summand on the righthand side must also be even.
But since it is entirely a sum of odd values, it must must contain an even
number of terms.  That is, there must be an even number of vertices with
odd degree.
\end{proof}

Two graphs with the same shape will of course have the same pattern of
vertex degrees -- that's one of things that ``same shape'' should imply.
More precisely, if $f$ is an isomorphism between two graphs, then it is
easy to show that $v$ and $f(v)$ have the same degree for any vertex $v$.
We say that the degree of a vertex is \emph{invariant} under graph
isomorphism.  Since $f$ is a bijection, it follows that isomorphic graphs
must have exactly the same numbers of vertices of any degree $d$.  That
is, the number of vertices of degree $d$ in a graph is an invariant under
isomorphism.  Isomorphic graphs must also have the same number of pairs of
vertices of degree $d_1$ and degree $d_2$ which are adjacent -- another
invariant under isomorphism.  If two graphs are found to have different
values of some invariant, then they are cannot be isomorphic.  Finding
such invariants can be a simple means to prove that two perhaps roughly
similar looking graphs, are not actually isomorphic (see Rosen, 7.3,
Examples 9, 10).

\subsection{Chromatic Number}

Time to discuss final exams.  The MIT Schedules Office needs to assign
a time slot for each final.  This is not easy, because some students
are taking several classes with finals, and a student can take only
one test during a particular time slot.  The Schedules Office wants to
avoid all conflicts, but wants to make the exam period as short as
possible.

This scheduling problem can be represented by a graph.  Let each
vertex represent a course.  Put an edge between two vertices if there
is some student taking both courses.  Identify each possible
time slot with a color.  For example, Monday 9--12 is red, Monday 1--4
is blue, Tuesday 9--12 is green, etc.

If there is an edge between two vertices with the same color, then a
conflict exam will have to be scheduled because there is a student who has
to take exams for the courses represented by the vertices, but the exams
are scheduled at the same time.  Everyone wants to avoid conflict exams,
so the registrar would like to color each vertex of the graph so that no
adjacent vertices have the same color; to keep exam period as short as
possible, the registrar would like to use the minimum possible number of
colors.  An example is shown in Figure~\ref{fig:exams}.

\begin{figure}[htbp]
\centering \includegraphics[height=2in]{figures/exams}
% \centerline{\psfig{figure=figures/exams.eps,height=2in}}
\caption{\em This graph represents the exam scheduling problem.  Each
vertex stands for a course.  An edge between two vertices indicates that a
student is taking both courses and therefore the exams cannot be scheduled
at the same time.  Each exam time slot is associated with a color.  A
schedule that creates no conflicts for any student corresponds to a
coloring of the vertices such that no adjacent vertices receive the same
color.}
\label{fig:exams}
\end{figure}

In general, the minimum number of colors needed to color the vertices of a
graph $G$ so that no two adjacent vertices are the same is called the {\em
chromatic number} and is written $\chi(G)$.  For example, if $G$ is the
3-cycle or triangle graph, then $\chi(G) = 3$.\footnote{$\chi$ is the
Greek letter ``chi'' --- pronounced ``he'' by the Greeks and ``kye'' by
(non-Greek) mathematicians and college fraternities.}

The only completely general way known for finding the chromatic number of
a graph is to exhaustively try all possible colorings; the exhaustive
approach really is exhausting, and it becomes prohibitive even for graphs
with only a few dozen vertices.  Sometimes we can take advantage of the
structure of special classes of graphs to get a better grip on their
colorings.  Also, we can at least put some general upper bounds on the
chromatic number.  For example, the chromatic number of an $n$-vertex
graph is certainly at most $n$, since every vertex could be assigned a
different color.

Suppose that we tried to do better by coloring vertices in an arbitrary
order, but using a new color only when forced to do so.  This strategy
lies behind the following recursive algorithm.  The input is a graph, and
the output is a graph with appropriately colored vertices.
\begin{itemize}

\item Pick a vertex $v$.  Remove $v$ and all incident edges from the
graph.

\item If the graph is not empty, color the remainder recursively.

\item Add $v$ back to the graph.  Color $v$ differently from all
neighbors, using a new color only if necessary.

\end{itemize}

\begin{theorem}
The preceding algorithm colors a graph with at most $p + 1$ colors,
where $p$ is the maximum degree of any vertex.
\end{theorem}

This theorem implies, for example, that a graph with thousands of
vertices, each of degree 3, requires at most 4 colors.  The proof is
surprisingly easy:

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate that the
preceding algorithm colors every $n$-vertex graph in which every vertex has
degree at most $p$ using at most $p + 1$ colors.

In the base case, $P(1)$, there is a single vertex with degree zero.
In this case, $p = 0$ and the algorithm requires $p + 1 = 1$ colors.

In the inductive step, assume $P(n)$ to prove $P(n+1)$.  Let $G'$ be
the graph obtained from $G$ by removing vertex $v$ and incident edges.
No vertex in $G'$ has degree greater than $p$, since removing a vertex
and incident edges can not increase the degree of any other vertex.
(This is what we had to check to avoid ``buildup error'' --- see below.)
By induction, the algorithm (applied recursively) colors $G'$ with at
most $p + 1$ colors.  Now we add back vertex $v$.  Since $v$ has at
most $p$ neighbors and there are $p + 1$ colors available, there is
always one color left over for vertex $v$.  Therefore, the algorithm
colors $G$ with at most $p + 1$ colors.
\end{proof}

\subsection{Paths in Graphs}

Is a graph all in one piece or composed of several pieces?  To walk
from one vertex to another, how many edges must one cross?  Are there
many different routes or just one?  These are questions about
\emph{connectivity}.

%\subsubsection*{Definitions}

A {\em path} in a digraph from a vertex $u$ to a vertex $v$ is a sequence of
$k\geq 1$ edges 
\[(v_0, v_1), (v_1,v_2), \ldots, (v_{k-1}, v_k)\]
such that $v_0 =u$ and $v_k = v$.  A path may contain the same edge
multiple times.  The {\em length} of the path is $k$.  The sequence of
\emph{sequence of vertices on the path} is the sequence $v_0, v_1, v_2,
\dots, v_k$.  Vertex $u$ is said to be {\em connected} to vertex $v$ iff
$u=v$ or there is a path from $u$ to $v$.  The definitions for simple
graphs are the same except that the ordered pair $(v_i,v_{i+1})$ is
replaced by the unordered set $\set{v_i,v_{i+1}}$.  A path is {\em simple}
when no vertex occurs more than once in the sequence of vertices on the
path.

\begin{lemma}\label{simplepath}
If vertex $u$ is connected to vertex $v\neq u$ in a graph, then there is a
simple path from $u$ to $v$.
\end{lemma}

The proof provides a nice example illustrating the Least Number Principle.

\begin{proof}
Since $u\neq v$, there is a path from $u$ to $v$.  By the Least Number
Principle, there must be a minimum length path
\[
(v_0, v_1), (v_1,v_2), \ldots, (v_{k-1}, v_k)
\]
from $u$ to $v$.  We claim this path must be simple.  This is clearly the
case if $k=1$, since then the path consists of a single edge from $u$ to
$v$.  Given that $k>1$, we prove the claim by contradiction.

Namely, assume that some vertex on the path occurs twice.  More precisely,
there are $i,j \in \naturals$ such that $i<j\leq k$ with $v_i= v_j$.  Then
removing the sequence of $j-i>0$ edges
\[
(v_i,v_{i+1}),\dots,(v_{j-1}, v_j)
\]
from the path yields a path from $u$ to $v$ of length $< k$, contradicting
the fact that $k$ is minimal.
\end{proof}

A {\em cycle} (also called a {\em circuit}) in a graph is a path from a
vertex to itself, i.e. a sequence of edges $(u, v_1),\dots, (v_{k-1}, u)$.
A {\em simple cycle} is a cycle in which only the first and last vertex
occurring on the path are the same and no edge occurs twice\footnote{The
condition that no edge occurs twice is only needed for undirected graphs,
where we don't want going back and forth on the same edge to count as a
simple cycle.}.  Another way to say this is that a simple cycle is either
a self-loop or is a cycle which becomes a simple path when its first or
last edge is deleted.

%%EXAMPLES OF PATH, SIMPLE PATH, CYCLE, SIMPLE CYCLE

\subsection{Adjacency Matrices}

We defined a graph in terms of a set of vertices and a set of edges.
A graph can also be described by a matrix.  

Let $v_1,\dots,v_n$ be list of the vertices of a digraph, $G$.  The {\em
adjacency matrix} of $G$ is an $n \times n$ matrix of zeroes and ones.
The entry in row $i$ and column $j$ of the matrix is one iff there is an
edge from $v_i$ to vertex $v_j$. 

%% Couldn't access picture from Spring 99 due to stupid directory permissions
% An example is shown in Figure~\ref{fig:matrix}.

% \begin{figure}[htbp]
% %%\centerline{\psfig{figure=figures/matrix.eps,height=2.0in}}
% CANNOT FIND PICTIURE
% \caption{\em This is a graph with list of vertices (1, 2, 3, 4), and its
% associated $4\times 4$ adjacency matrix.  The entry in row $i$ and column
% $j$ of the matrix is a 1 if there is an edge $(i, j)$ in the graph.  All
% other entries are 0.}
% \label{fig:matrix}
% \end{figure}

Weighted or labelled digraphs can also be described well by matrices: let
the label of edge $(v_i,v_j)$ be the matrix entry in row $i$, column $j$.

Observe that in a digraph with $n$ vertices, the paths from a vertex, $u$,
to a vertex, $v$, can be partitioned (divided into nonoverlapping groups)
according to their next-to-last vertex.  That is, the paths from $u$ to
$v$ can be partitioned into at most $n$ sets, one for each vertex adjacent
to $v$.  The $k$th set consists of those paths, if any, which begin with a
path from $u$ to $v_k$ followed by an edge from $v_k$ to $v$.  Matrix
multiplication can now be given a neat graphical interpretation.

\begin{theorem}
Let $A$ be the $n \times n$ adjacency matrix of a digraph $G$, and let
$A^m$ be its $m$th power for $m>0$.  Then $A^m_{ij}$, the $ij$th entry
of $A^m$, is exactly equal to the number of distinct paths of length $m$
from vertex $i$ to vertex $j$.
\end{theorem}

\begin{proof}
By induction on $m$.

Base case $m=1$ holds by definition.

To prove the induction case, note that from the partitioning of paths
by next-to-last vertices described above, the number of paths from
$v_i$ to $v_j$ of length $m>1$ is the sum of the number of paths of
length $m-1$ from $v_i$ to $v_k$ with the sum taken over all $k$ such
that there is an edge from $v_k$ to $v_j$.  This is the same as
\[\sum_{k=1}^n \card{\set{\mbox{length $m-1$ paths from $v_i$ to $v_k$}}}A_{kj}\]
But by induction, $\card{\set{\mbox{length $m-1$ paths from $v_i$ to
$v_k$}}} = A^{m-1}_{ik}$, and $\sum_{k=1}^n A^{m-1}_{ik} A_kj =
A^{m}_{ij}$, so indeed $A^{m}_{ij}$ is the number of paths from $v_i$
to $v_j$ of length $m$.
\end{proof}


\subsection{Connectedness}

Clearly if $u$ is connected to $v$, and $v$ is connected to $w$, then $u$
is connected to $w$.  That is, the ``connected'' relation is {\em
transitive}.  It is also {\em reflexive} since every vertex is by
definition connected to itself.  If the graph is simple, then obviously
$u$ is connected to $v$ iff $v$ is connected to $u$, so the relation is
\emph{symmetric}.  That is, ``connected'' is actually an {\em equivalence
relation} ({\em cf.} Rosen, section 6.5) on the set of vertices of a
simple graph.

A graph is {\em connected} if there is a path between every pair of
distinct vertices.  For example, referring back to
Figure~\ref{fig:zoo}, the empty graph is disconnected, but all others
shown are connected.

 \iffalse

 %  The examples of subgraphs do not fit the definition; the notion of
 %  isomorphism is needed here.


 A {\em subgraph} of a graph $G = (V, E)$ is a graph $G' = (V' , E')$
 such that $V' \subseteq V$ and $E' \subseteq E$.  For example, a
 triangle is a subgraph of $K_4$ (the complete graph on four vertices),
 but not of $C_4$ (a cycle with four vertices).
 \fi

A subset of the vertices of an undirected graph is a {\em connected
component} of the graph if it consists of precisely all the vertices
connected to some single vertex.  That is, the connected components of a
graph are the \emph{equivalence classes} of the connectedness relation.
In particular, every vertex of a simple graph belongs to exactly one
connected component, and for any two vertices $v_1, v_2$, either the
component of $v_1$ is the same as the component of $v_2$ (when $v_1$ is
connected to $v_2$), or the two components have no elements in common
(when $v_1$ is not connected to $v_2$).

Another way to say that a subset of vertices is a connected component is
to say that every pair of vertices in the subset is connected, and the
subset is {\em maximal} for this property, that is, no new vertex can be
added to the subset which keeps the subset connected.

So a simple graph is connected iff it has exactly one connected component.
The empty graph on $n$ vertices has $n$ connected components.  A graph
with three connected components is shown in Figure~\ref{fig:3comp}.  We
let $\gamma(G)$ be the number of connected components in a simple graph,
$G$.

\begin{figure}[htbp]
\centering \includegraphics[height=1.5in]{figures/3comp}
% \centerline{\psfig{figure=figures/3comp.eps,height=1.5in}}
\caption{\em This is a picture of a graph with 3 connected components.}
\label{fig:3comp}
\end{figure}

\subsubsection*{A False Theorem about Connectivity}

If a graph is connected, then every vertex must be adjacent to some
other vertex.  Is the converse of this statement true?  If every
vertex is adjacent to some other vertex, then is the graph connected?
The answer is no.  In fact, the graph with three connected components
shown in in Figure~\ref{fig:3comp} is a counterexample.  So what is
wrong with the following proof?

\begin{falsethm}
If every vertex in a graph is adjacent to another vertex, then the
graph is connected.
\end{falsethm}

Nothing helps a false proof like a good picture; see
Figure~\ref{fig:false}.

\begin{figure}[htbp]
\centering \includegraphics[height=1.5in]{figures/false}
% \centerline{\psfig{figure=figures/false.eps,height=1.5in}}
\caption{\em This picture accompanies the false proof.  Two situations
are depicted.  In one, vertices $x_1$ and $x_2$ both are among the
vertices of $G$, and so there is a connecting path by induction.
In the second, $v = x_1$ and $x_2$ is a vertex of $G$.
In this case there is a connecting path because there is an edge from
$v$ to $u$ and a path in $G$ from $u$ to $x_2$ by induction.}
\label{fig:false}
\end{figure}

\begin{proof}
The proof is by induction.  Let $P(n)$ be the predicate that if every
vertex in an $n$-vertex graph is adjacent to another vertex, then the
graph is connected.  In the base case, $P(1)$ is trivially true
because there is only one vertex.

In the inductive step, we assume $P(n)$ to prove $P(n+1)$.  Start with an
$n+1$-vertex graph, $G'$, in which every vertex is adjacent to another
vertex.  Now take some vertex $v$ away from the graph and let the $G$ be
the remaining graph.  By assumption $v$ is adjacent in $G'$ to one of the
$n$ vertices of $G$; call that one $u$.

Now we must show that for every pair of distinct vertices $x_1$ and $x_2$
in $G'$, there is a path between them.  If both $x_1$ and $x_2$ are
vertices of $G$, then since $G$ has $n$ vertices, we may assume by
induction it is connected.  So there is a path between $x_1$ and $x_2$.
Otherwise, one of the vertices is $v$ (say $x_1$) and the other, $x_2$ is
in $G$.  But $x_2$ is connected to $u$ by induction, so there is a path
from $x_1$ to $u$ to $x_2$ as shown in the figure.
\end{proof}

The error is in the statement ``\emph{since $G$ has $n$ vertices, we may
assume by induction it is connected.}''  The induction hypothesis does not
say that every $n$-vertex graph is connected, but only, ``{\em if every
vertex in an $n$-vertex graph is adjacent to another vertex,} then the
graph is connected''.  For example, if $G'$ is the graph with vertices 1,
2, 3, 4 and edges $\set{1,2}$ and $\set{3,4}$, then removing vertex 1 to
form $G$ leaves vertex 2 without an adjacent vertex in $G$, and we can't
conclude by induction that $G$ is connected (which of course it isn't).

This is a variant of ``buildup error.''  We're proving something about
graphs with the property that every vertex is adjacent to another vertex.
The argument implicitly assumes that any size $n+1$ graph with the
property can be built up from a size $n$ graph with the same property, but
not every such size $n+1$ graph can be built this way.

\iffalse
The error is in the statement ``\emph{since $G$ has $n$ vertices, we may assume
by induction it is connected.}''  The induction hypothesis does not say
that every $n$-vertex graph is connected, but only, ``{\em if every vertex
in an $n$-vertex graph is adjacent to another vertex,} then the graph is
connected''.  For example, if $G'$ is the graph with vertices 1, 2, 3, 4
and edges $\set{1,2}$ and $\set{3,4}$, then removing vertex 1 to form $G$
leaves vertex 2 without an adjacent vertex in $G$, and we can't conclude
by induction that $G$ is connected (which of course it isn't).

The core problem here is called ``buildup error'' and is a common source
of mistakes in inductive proofs.  Buildup error occurs when the induction
hypothesis $P(n)$ is itself an implication of the form $A(n) \Rightarrow
B(n)$.  In this instance, $A(n)$ is the statement, ``every vertex in an
$n$-vertex graph is adjacent to another vertex'' and $B(n)$ is the
statement, ``the graph is connected''.

In the inductive step of a correct proof, we assume $A(n) \Rightarrow
B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.  In an erroneous
proof, we assume $B(n)$ in order to prove $A(n+1) \Rightarrow B(n+1)$.
This is precisely what happened; we assumed, ``the graph is
connected'' rather than, ``if every vertex in an $n$-vertex graph is
adjacent to another vertex, then the graph is connected''.
\fi

\subsubsection*{A True Theorem about Connectivity}

If a graph has too few edges, then there cannot be a path between
every pair of vertices.  More generally, a graph with a very small
number of edges ought to have many connected components.  (Remember,
``many connected components'' does not mean ``very connected'';
rather, it means ``broken into many pieces''!)  The following theorem
generalizes these observations.

\begin{theorem}\label{-ec1}
Adding a single edge to a simple graph reduces the number of connected
components by at most one.  More precisely, let $G$ be a simple graph and
$G'$ be $G$ with the addition of a single edge between two vertices of
$G$.  Then $\gamma(G') \geq \gamma(G)-1$.
\end{theorem}

\begin{proof}
If the new edge is between two vertices which are already connected, then
the connectedness relation between vertices remains the same with or
without the edge, so $G$ and $G'$ have exactly the same connected
components and $\gamma(G') = \gamma(G)$.  If the new edge is between
vertices $v_1$ and $v_2$ which are not connected in $G$, then the
component of $v_1$ and the component of $v_2$ are distinct in $G$ and
become one component of $G'$.  The components of $G$ which contain neither
$v_1$ nor $v_2$ remain as connected components of $G'$.  The effect is
that the number of components in $G'$ is one less than in $G$,
\emph{viz.}, $\gamma(G') = \gamma(G)-1$.
\end{proof}

\begin{corollary}
For any simple graph $G=(V,E)$,
\[\gamma(G)\geq \card{V} - \card{E}.\]
\end{corollary}

For example, a graph with 0 edges and $n$ vertices has $n - 0
= n$ connected components.  A graph with 100 vertices and 35 edges
must have at least 100 - 35 = 65 connected components.

\begin{proof}
By induction on $\card{E}$.  (This may seem odd, because for $\card{E} >
\card{V}$, the theorem says that the number of connected components is
greater than some negative number!  This is useless, but certainly true,
so there is no harm.)

The induction hypothesis will be $P(k)$: any graph $G=(V,E)$ with $k$
edges has at least $\card{V} - k$ connected components.

In the base case, $P(0)$ holds because in a graph with 0 edges, each
vertex is a connected component, so $\gamma(G) = \card{V} \geq \card{V} -
0$.

In the inductive step, let $G'=(V',E')$ be a graph with $k+1$
edges.  We want to prove that $\gamma(G') \geq \card{V'} - (k+1)$.

Pick some edge of $G'$ and let $G$ be $G'$ with the chosen edge removed.
By the lemma above, 
\[\gamma(G') \geq \gamma(G)-1.\]
By induction we may assume that $P(k)$ is
true, and since $G$ has $k$ edges, we have
\[\gamma(G)\geq \card{V} - k.\]
But $\card{V} = \card{V'}$, so
\[\gamma(G') \geq \gamma(G)-1 \geq (\card{V'} -k) -1 = \card{V'} -(k+1).\]
\end{proof}

Since a graph $G$ is connected iff $\gamma(G)=1$, we conclude immediately:

\begin{corollary}\label{cev1}
If a simple graph $G=(V,E)$ is connected, then
\[\card{E} \geq \card{V}-1.\]
\end{corollary}


\section{Trees}

Tree are an important special type of graph for CS applications.  We
have just seen that $n-1$ edges are required for connectivity. They
are sometime sufficient, for example if we connect all the nodes in a
line. Let's explore the smallest connected graphs.  What is a good
notion of smallest? No wasted edges.

\begin{definition}
  A \emph{tree} is a connected graph with no cycles.
\end{definition}

\begin{figure}
  \centerline{\includegraphics[height=2in]{figures/tree}}
  \caption{This tree has 11
    \emph{leaves}, which are defined as vertices of degree at most one.
    The remaining 7 vertices are called \emph{internal nodes}.}
  \label{fig:tree}
\end{figure}

The vertices in a tree can be classified into two categories.
Vertices of degree at most one are called \emph{leaves}, and vertices
of degree greater than one are called \emph{internal nodes}.

Trees are often drawn as in Figure~\ref{fig:tree} with the leaves on
the bottom and a single node (called the \emph{root} at the top).
Keep this convention in mind; otherwise, phrases like ``all the
vertices \emph{below}'' will be confusing. \footnote{(The English
mathematician Littlewood once remarked that he found such directional
terms particularly bothersome, since he habitually read mathematics
reclined on his back!)}

Trees arise in many problems.  Family trees are an example---each node
is a person, and there is an edge between any parent and child.
Similarly, the file structure in a computer system can often be
represented by a tree.  In this case, each internal node corresponds
to a directory, and each leaf corresponds to a file.  If one directory
contains another, there there is an edge between the associated
internal nodes.  If a directory contains a file, then there is an edge
between the internal node and a leaf.  In both family trees and
directories, there can be exceptions that make the graph not a
tree---relatives can marry and have children, while directories
sometimes use soft links to create multiple directory entries for a
given file.


There are in fact many different equivalent ways of defining trees
formally.

\begin{theorem}
For any simple graph $G=(V,E)$, the following are equivalent:
\begin{enumerate}
\item \label{ev1} $G$ is connected and $\card{E} = \card{V}-1$.
\item \label{-e} $G$ is connected, but removing any edge from $G$ leaves a
      disconnected graph.
\item \label{ac} $G$ is connected and acyclic.
\item \label{1p} There is a unique simple path between any two distinct
      vertices of $G$.
\end{enumerate}
\end{theorem}

Of course it would be a waste of effort to prove that each statement
implied all the others -- twelve different implications.  Instead, we
prove that each implies the next, and the fourth implies the first -- only
four implications.  Some of the implications among these properties are
harder to prove directly than others, so the order in which they are
listed will affect the simplicity of the four direct implications to be
proved.  You might wonder how to pick an order which leads to simple
proofs.  There was no trick used here, just trial and error (over several
hours) to find an order which allowed the simplest proofs -- and there may
well be a still simpler one we overlooked.

\begin{proof}
\begin{itemize}

\item (Property~\ref{ev1}.\ implies Property~\ref{-e}.) This follows
immediately from Corollary~\ref{cev1}.

\item (\ref{-e}.\ implies \ref{ac}.) By contradiction.

Suppose Property~\ref{-e}.\ holds, but $G$ has a simple cycle.  Then
removing the first edge in the cycle leaves a simple path connecting all
the vertices in the cycle.  This implies that the connected component of
the vertices in the cycle is the same after the edge is removed as it was
in $G$.  Since there was only one connected component to begin with, there
is still only one after the edge is removed.  That is, the graph is still
connected, contradicting Property~\ref{-e}.

\item (\ref{ac}.\ implies \ref{1p}.) By contradiction.

Suppose Property~\ref{ac}.\ holds, but there are distinct simple paths
between two vertices of $G$.  That is, there are vertices $u\neq v$ and
distinct simple paths $P_1$ with vertices $u, w_1, \dots, w_n, v$ and
$P_2$ with vertices $u, w'_1, \dots, w'_{n'}, v$.  Among all such $u,v,
P_1,P_2$, we can, by the Least Number Principle, choose some for which
$P_1$ is shortest.

Suppose $P_1$ a single edge, that is $P_1 = \set{u,v}$.  If $P_2$ started
with this same edge, then $P_2$ without its first edge would be a simple
cycle from $v$ to $v$, contradicting proposition~\ref{ac}.  On the other
hand, if $P_2$ did not start with $\set{u,v}$, then since $\set{u,v}=
\set{v,u}$, the path starting with this edge followed by the edges in
$P_2$ form a simple cycle from $v$ to $v$, again contradicting
proposition~\ref{ac}.

Hence, $P_1$ is of length greater than one, and $1 \leq n \leq n'$.
Moreover, the first edge of $P_1$ must differ from the first edge of
$P_2$, since otherwise $w_1 = w'_1$ and $P_1$ and $P_2$ without their
first edges would be distinct paths between $w_1$ and $v$, contradicting
the minimality of the length of $P_1$.

Now we claim that no vertex $w_i$ internal to $P_1$ is the same as any
vertex $w'_j$ internal to $P_2$.  This follows because if $w_i = w'_j$,
then the two paths $u, w_1, \dots, w_i$ and $u, w'_1, \dots, w'_j$ between
$u$ and $w_i$ would be distinct because their first edges differ, and the
first path would be shorter than $P_1$, again contradicting the minimality
of $P_1$.  So no $w_i$ can equal any $w'_j$.  Hence the concatenation
of all but the last vertex of $P_1$ with the reversal of $P_2$, namely,
\[u, w_1, \dots, w_n, v, w'_{n'}, \dots, w'_1, u\]
is a simple cycle, contradicting proposition~\ref{ac}.

\item (\ref{1p}.\ implies \ref{ev1}.)

By strong induction on $\card{V}$.  The induction hypothesis is that 
\ref{1p} implies \ref{ev1} for all graphs with $n$ vertices.

(Base case: $\card{V} = 1$)  
Property~\ref{ev1}.\ is immediate if $G$ has one vertex.

(Induction) Suppose \ref{1p}.\ implies~\ref{ev1}.\ for all graphs with $1
\leq k \leq n$ vertices.  Let $G$ be a graph with $n+1$ vertices
satisfying proposition\ref{1p}.  We must show that~\ref{ev1}.\
holds for $G$.

Since $G$ has $n+1 \geq 2$ vertices, and any two vertices are connected by
a simple path, $G$ certainly has at least one edge.  Let $G'$ be the graph
which is left after removing some edge, $\set{u, v}$, from $G$.

If there was still a path between $u$ and $v$ in $G'$, then by
Lemma~\ref{simplepath} there would a simple path between $u$ and $v$ in
$G'$.  But then in $G$, this path and the edge $\set{u, v}$ would be
distinct simple paths between $u$ and $v$, contradicting~\ref{1p}.  So
$G'$ cannot be connected.  Let $G_i =(V_i, E_i)$ for $1 \leq i \leq n \geq
2$ be the set of connected components of $G'$.

Now each connected component $G_i$ still has unique simple paths and has
fewer vertices than $G$, so by strong induction $\card{E_i} = \card{V_i} -
1$.  Now we have
\[\begin{array}{lclclcl}
\card{V} & = & \sum_{i=1}^n \card{V_i} & = & \sum_{i=1}^n (\card{E_i} +  1)\\
         & = & (\sum_{i=1}^n \card{E_i}) + n & = & \card{E'} + n\\
         & \geq & \card{E'} + 2 & = & (\card{E} - 1) + 2 & = & \card{E} + 1.
\end{array}\]
That is, $\card{E} \leq \card{V} - 1$.  But since $G$ is connected, we
have from Corollary~\ref{cev1} that $\card{E} \geq \card{V} - 1$.  So
$\card{E} = \card{V} - 1$.

\end{itemize}
\end{proof}


\section{Euler Tours}

The Koenigsberg bridge problem: can we cross all seven bridges in the
town of Koenigsberg
exactly once, without repeats, returning to our starting point?
%[[[Could use an improved picture.]]]
\begin{verbatim}

          |    |           |     /
      ----|----|---   -----|----/
     /    |    |   \ /     |  
----<             --X--     
     \    |    |   / \     |
      ----|----|--/   \----|----\
          |    |           |     \

\end{verbatim}
This problem has a graph representation as shown in Figure~\ref{fig:euler} \\

\begin{figure}[htbp]
\centerline{\includegraphics[height=1.5in]{figures/euler}}
\caption{Graph representation for the Koenigsberg bridge problem.}
\label{fig:euler}
\end{figure}

Stated as a general graph theory problem, the problem is to construct
a circuit of the graph that traverses every edge exactly once.  (Each
edge will be traversed in exactly one direction.)  (Actually, note
that the Koenigsberg graph is technically a multigraph, not a simple
graph, because it has multiple edges between two of the pairs of
vertices.  We could change this into a simple graph by adding some
extra vertices in the middle of the repeated edges.)  Euler, in 1736,
proved that it can't be done.  So we call such tours ``Euler Tours.''

\begin{definition}
An Euler tour of an undirected graph $G$ is a circuit that traverses
every edge of $G$ exactly once.
\end{definition}

\begin{theorem}
If undirected graph $G$ has Euler tour, then $G$ is connected and every
vertex has even degree.
\end{theorem}
\begin{proof}
Direct every edge according to tour.  We enter a vertex as many times
as we leave it.  So every vertex must have indegree
equal to outdegree.  So total even.
\end{proof}

It follows that there is no tour of Koenigsberg, because there is an
odd-degree vertex.

100 years later, Hierholzer proved the converse (that's the trouble
with coming second---no one remembers your name!)
\begin{theorem}
If $G$ is connected and every node has even degree, 
then it has an Euler tour.
\end{theorem}

\begin{proof}
  If $G$ has only one node then it has a trivial (1-node) Euler tour.
  So assume $G$ has at least two nodes.  Then $G$ must have at least
  one edge (to be connected).  Starting from this edge, construct a
  circuit with no repeated edges: trace from node to node until we
  cannot go any further on an unused edge. Because every node has even
  degree, this can only happen when we return to the node we started
  at (every other node we reach will have another edge by which we may
  leave).

  Let $C$ be the longest circuit without any repeated edges.  If $C$
  includes all the edges of $G$, we are done.  So assume it doesn't.
  Let $H$ be the subgraph of $G$ consisting of all the edges of $G$
  that aren't in $C$, and all the nodes of $G$ that are incident on
  these edges.  We claim that some node $u$ in $H$ is also in $C$.
  Why?  Because $G$ is connected.

  Now choose any edge of $H$ incident upon $u$.  Starting with that
  edge, construct a cycle in $H$, following the same procedure as
  above.  Eventually, it has to get back to its starting point $u$.
  Now we have two cycles with disjoint edge sets and a common vertex
  $u$.  Splice them together to get a larger cycle than $C$.  The
  contradicts the choice of $C$ as maximum.
\end{proof}


% \section{Euler Circuits}

% We can generalize Euler tours to directed graphs.  
% \begin{definition}
% An Euler Circuite of a directed graph $G$ is a circuit in $G$ that
% traverses each edge of $G$ exactly once. 
% \end{definition}

% \begin{figure}[htbp]
% \centerline{\includegraphics[height=1.5in]{figures/eulerdigraph}}
% \caption{An Euler circuit exists if we add the edge (3,2)}
% \label{fig:EulerCir}
% \end{figure}

% \begin{theorem}
%   Suppose $G$ is a weakly connected digraph.  Then $G$ has an Euler
%   circuit if and only if the in-degree and out-degree of each vertex
%   are equal.
% \end{theorem}
% \begin{proof}
%   We first prove the ``only if'' direction.  Assume $G$ has an Euler
%   circuit.  Fix any node $u$.  It occurs some number $k$ of times in
%   the circuit.  Each time it occurs, it has one edge in and one edge
%   out.  This uses up all the edges of the graph, and no edge is used
%   more than once.  So each vertex has equal in-degree and out-degree.

%   Now we prove the ``if'' direction: Assume $G$ is a weakly connected
%   digraph such that each node's in-degree and out-degree are equal.

%   If the edge set is empty, then weak connectivity implies that there
%   can be only one node.  That node by itself constitutes a trivial (0
%   edge) Euler circuit.  So assume that the edge set is nonempty.

%   In this case, we can show that there exists some circuit with no
%   repeated edges.  We show this by starting with any edge, and tracing
%   from node to node along unused edges, until we reach a node for
%   which all its outgoing edges were traced. This is the node we
%   started with, since whenever we reach another node the number of
%   incoming edges that have been traversed is one larger than the
%   number of outgoing edges that have been traversed.

%   Now choose a maximum length circuit in $G$ with no repeated edges;
%   call it $C$.  If $C$ includes all the edges, we're done.  So assume
%   that it doesn't.

%   Let $H$ be the subgraph of $G$ consisting of all the edges of $G$
%   that aren't in $C$, and all the nodes of $G$ that are incident on
%   these edges.  Claim that some node in $H$ is also in $C$.  For if
%   not, $G$ is not weakly connected (since we can partition the set of
%   nodes to the nodes in $H$ and in $C$ and there is no edge connecting
%   these two sets of nodes).  Choose such a node, $u$.

%   The fact that $u$ has an incoming or outgoing edge that was not
%   traversed, implies that $u$ must have an outgoing edge that was not
%   traversed (the number of traversed incoming and outgoing edges must
%   be equal).  Starting with that outgoing edge, construct a cycle in
%   $H$, following the same procedure as above.  Eventually, it has to
%   get back to its starting point.

%   Now we have two cycles with disjoint edge sets and a common vertex,
%   $u$.  We can splice them together to get a larger cycle than $C$.
%   But this contradicts the choice of $C$ as maximum.
% \end{proof}


\section{Hamiltonian Circuits}

A slightly different question: is there a simple circuit that
traverses every \emph{vertex} exactly once?  Such a circuit is called
a \emph{Hamiltonian circuit} (Hamiltonian cycle).  Similarly, a simple
path that traverses every vertex exactly once is a \emph{Hamiltonian
path}.

The Rosen text has some simple conditions for determining the existence or
nonexistence of Hamiltonian cycles in many cases.  But although there's
only a small change in switching the question from Euler circuits to
Hamiltonian circuits, these two kinds of circuits have dramatically
different properties.  Specifically, while determining the existence of a
Euler circuit in a graph is easy, determining Hamiltonian circuite is very
complicated.

In fact, no simple criterion is known for determining whether or not a
graph has a Hamiltonian circuit.  And it's not merely that we're ignorant
of a criterion: there are powerful theoretical arguments supporting the
belief that there \emph{is no} simple criterion for Hamiltonian circuits.
The Hamiltonian circuit problem is an example of an \emph{NP-complete}
problem.  Not only don't we expect to find a simple criterion for solving
any \emph{NP}-complete problem, but we don't even expect there to be a
not-so-simple criterion which could still be checked quickly by a computer
program.  The theory of \emph{NP}-completeness is a basic topic in
Algorithms and Computability courses; we shall not describe it further in
these Notes.

\begin{optional}
Here is a slightly harder result.
\begin{lemma}
Any graph with $n$ vertices, $n \geq 3$, in which the minimum degree
of each node is at least $n/2$, has a Hamiltonian circuit.
\end{lemma}

\iffalse
Proof in earlier Notes was wrong, because it assumed that the new vertex's
neighbors all had to be on the cycle.  This one comes from Bondy and
Murty, p. 54-55.
\fi

\begin{proof}
By contradiction.
Suppose some graph has $n$ vertices, $n \geq 3$, and the minimum degree
of each node is at least $n/2$, but that graph does not have a
Hamiltonian circuit.

If we add edges to this graph one at a time, we eventually end up with
a complete graph, which does have a Hamiltonian circuit (why?). 
Somewhere in the process of adding edges, we have a graph, $G$,
that doesn't have a Hamiltonian circuit, but adding one more edge
$(u,v)$ yields a graph, $G'$, that does have a Hamiltonian circuit.
We'll get a contradiction for this $G$.

Since $G$ plus the one edge $(u,v)$ has a Hamiltonian circuit, $G$ alone
has a Hamiltonian path from $u$ to $v$ (just remove the one new edge).
Say the path is $u = u_1,\ldots, u_n = v$; by definition this path
includes all the nodes of $G$.

Now let's play with that path and turn it into a circuit, to get a
contradiction.  We will use the fact that $u$ and $v$ each have degree
at least $n/2$ to produce two edges to replace one edge $(u_i,u_{i+1})$ on
the path\dots.

%%\begin{figure}[htbp]
%% \centerline{\psfig{figure=/a/class/6.042/fall00/newlectures/figures/hamilton%% ian.eps,height=2in}}
%% \centering \includegraphics[height=2in]{figures/hamiltonian}
%%\caption{Converting the Hamiltonian path into a circuit}
%%\label{fig:hamiltonian}
%%\end{figure}

Now let's count: Of the $n-2$ intermediate nodes on the path
$u_2,\ldots,u_{n-1}$ (all but the first and last) we know that at least
$n/2$ are neighbors of $u$, and at least $n/2$ are neighbors of $v$.  So
it can be shown that there are two adjacent nodes, $u_i$ and $u_{i+1}$,
where $u_i$ is a neighbor of $v$ and $u_{i+1}$ is a neighbor or $u$.
Postpone showing this for a minute\dots.

Then cut and add edges, to produce a Hamiltonian circuit,
contradiction.

Now, how do we get $u_i$ and $u_{i+1}$?
Just count how many are in various sets.  Use a little trick:

Let $S$ be $\{ i: u_{i+1} \mbox{ is a neighbor of } u \}$.

Let $T$ be $\{ i: u_i \mbox{ is a neighbor of } v \}$.

Each of $S$ and $T$ has at least $n/2$ elements.  Since there are only
$n-2$ possible values of $i$, some $i$ must be in both sets.  That is,
$u_i$ is a neighbor of $v$ and $u_{i+1}$ is a neighbor of $u$.
\end{proof}

This gives a special class of graphs with Hamiltonian circuits.
But no one has nice criteria for finding Hamiltonian circuits in
general, or for determining if they exist. 
\end{optional}
\end{document}


%% OLD STUFF

\section{Scheduling Courses}

We describe an application of graphs to a scheduling problem.  The example
also highlights a special kind of digraph called a {\em directed acyclic
graph} or {\em DAG}; a DAG is simply a digraph that does not contain a
(directed) cycle.

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]
\centering \includegraphics[height=3in]{figures/dag}
% \centerline{\psfig{figure=figures/dag.eps,height=3.0in}}
\caption{\em This is a picture of a directed acyclic graph.  Vertices
are labeled with course names.  An edge from $u$ to $v$ indicates that
course $u$ is a prerequisite for course $v$.}
\label{fig:dag}
\end{figure}

This example is a DAG.  Of course it is possible that the faculty in
charge of courses created a cycle of prerequisites; this would mean that
it was impossible to fulfill the prerequisites of any of the courses in
the cycle before taking the course.  Presumably this would not be the
intention of the faculty, so we assume that the whatever the prerequisite
requirements may be, they do not have cycles; so the digraph corresponding
to the prerequisites will always be a DAG.

The connectedness relation of a DAG is a {\em partial order}.  The
example in Figure~\ref{fig:dag} suggests the reason for this name.  The
arcs in this graph restrict the order in which a student may take classes.
For example, 6.001 must be taken before 6.003.  Of course, the student
still has some choice about the order; for this reason, the set of classes
is said to be ``partially'' ordered by this system of prerequisites.  If
we write $u \succeq v$ to mean that $u=v$ or there is a directed path from
vertex $u$ to $v$, then the relation $\succeq$ is obviously
\emph{transitive}: 
\[ [u \succeq v \wedge v \succeq w] \implies u \succeq w,\]
and \emph{antisymetric}:
\[ [u \succeq v \wedge v \succeq u] \implies u = v.\]
Formally, a partial order on a set is just a binary relation which is
transitive and antisymetric\footnote{Rosen also requires that a partial
order be \emph{reflexive}: $v \succeq v$ for all $v$.  In 6.042 we will
not always insist on reflexivity.  For example, we will consider the
relation $v \succ u$ --- defined to mean that there is a directed path
(which by definition is of \emph{positive} length) from vertex $u$ to $v$
--- to be a nonreflexive partial order on the vertices of a DAG.  Note
that the connectedness relation, $\succeq$, of a DAG is in fact reflexive
by our definition, because we explicitly specify that every vertex is
connected to itself.}

Two elements $u$ and $v$ are said to be {\em comparable} under a partial
order, $\succeq$, iff $u \succeq v \vee v \succeq u$.  When the partial
order is the one from connectedness in a DAG, vertices $u,v$ are
comparable precisely when $u=v$ or there is a directed path from $u$ to
$v$ or vice-versa.  Otherwise, $u$ and $v$ are incomparable.  For example,
18.01 and 6.002 are comparable since there is a directed path from 18.01
to 6.002.  However, 18.01 and 8.01 are incomparable because there is no
directed path from one to the other.

{\bf Problem}:  How many terms are necessary to complete all of the
courses in Figure~\ref{fig:dag}, assuming prerequisites are observed,
but course load is no issue?

The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
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, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.

{\bf Class exercise}: Explain why every finite DAG containing at least one
edge has a longest path.

{\bf Solution}: It follows directly from the Least Number Principle that
every nonempty set of natural numbers bounded above by some real number
has a \emph{maximum} element.  But no path in a DAG can be as long as
$\card{V}$, because any path of this length would have to repeat some
vertex and so would contain a cycle.  So the set of path lengths is
bounded above and is nonempty because the edge in the DAG is a path of
length one.  Hence, there is a maximum length path.


\medskip

A {\em chain} in a partial order, $\succeq$, is a single element or a
decreasing sequence of elements.  That is, $a_1, a_2, \dots, a_n$ is a
chain providing
\[
a_{1} \succ a_2 \succ \dots \succ a_n.
\]
Here we have written $a \succ b$ to mean $a \succeq b \wedge a \neq b$.
So every path in a DAG is a chain in the connectedness partial order of
the DAG.

An \emph{antichain} in a partial order is a set of elements no two of
which are comparable.  In a DAG, an antichain is a set of vertices with no
paths connecting any two of them.  For example, in the course-prerequisite
DAG, an antichain is a set of courses that can be taken in any order -- or
simultaneously -- as long as their other prerequisites have been met.

We let $t$ be the number of vertices in the longest chain in the graph.
This chain must be a path (Why?).  Now at least $t$ terms are necessary to
complete all the courses, because at most one course on the chain can be
taken each term.

We would now like to show that there is a schedule for taking courses
which achieves the minimum number of terms, $t$.  In particular, the
following theorem provides the required schedule.

\begin{theorem}
If the longest path in a DAG $G$ has length $t-1$, then the vertices can
be partitioned into a sequence of $t$ blocks such that any edge into a
vertex must start at a vertex from an earlier block.
\end{theorem}

This theorem implies that $t$ academic terms are sufficient to take all
the courses.  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.

\begin{proof}
Define the \emph{depth} of a vertex to be the length of the longest path
in the DAG which ends at the vertex (vertices with in-degree zero have
depth zero).  (There always is such a longest path by the same argument
used above to find a longest path in the whole DAG.)  For $0\leq i <
t$, let the $i$th block, $A_i$, consist of all vertices of depth $i$.  So
every vertex is in a unique block.  Moreover, each block is nonempty.  In
other words, the $A_i$'s partition the set of vertices.

The theorem will now follow if we show is that for all $a \in A_i$, if
there is a path of positive length from $b$ to $a$, then $b \in A_j$ for
some $j<i$.  We prove this by contradiction.

So suppose there is a path of positive length from $b$ to $a$, that $a \in
A_i$, and $b \not\in A_j$ for all $j<i$.  Since $b$ is in some block,
$A_k$, we conclude that $k\geq i$, so there is a path ending at $b$ of
length $\geq i$.  If we append this path to the positive length path from
$b$ to $a$, we obtain a path ending at $a$ of length $> i$, contradicting
the fact that the longest path to $a$ is of length $i$.

\end{proof}

{\bf Class exercise}: Explain why each block must be an antichain.

Since the blocks are antichains, we can conclude:
\begin{corollary}
Every partially ordered set with $n$ elements has a chain of length at
least $t$ or an antichain of size at least $\ceil{n/t}$, for every $t$
such that $1 \le t \le n$.
\end{corollary}

