\section{Adjacency Matrices}

A graph can be represented by an \term{adjacency matrix}.  In
particular, if a graph has vertices $v_1, \ldots, v_n$, then the
adjacency matrix is $n \times n$.  The entry in row $i$, column $j$ is
1 if there is an edge $\edge{v_i}{v_j}$ and is 0 if there is no such
edge.  For example, here is a graph and its adjacency matrix:

\mfigure{!}{1.5in}{adjacency-matrix}

The adjacency matrix of an undirected graph is always symmetric about
the diagonal line running from the upper left entry to the lower
right.  The adjacency matrix of a directed graph need not be
symmetric, however.  Entries on the diagonal of an adjacency matrix
are nonzero only if the graph contains self-loops.

Adjacency matrices are useful for two reasons.  First, they provide
one way to represent a graph in computer memory. 
Second, by mapping graphs to the world of matrices, one can bring all
the machinery of linear algebra to bear on the study of graphs.  (For
example, one can analyze a highly-prized quality of graphs called {\em
expansion} by looking at eigenvalues of the adjacency matrix.)

Here we prove a simpler theorem in this vein.  If $M$ is a matrix,
then $M_{ij}$ denotes the entry in row $i$, column $j$.  Let $M^k$
denote the $k$-th power of $M$.  As a special case, $M^0$ is the
identity matrix.

\begin{theorem}
Let $G$ be a digraph (possibly with self-loops) with vertices $v_1,
\ldots, v_n$.  Let $M$ be the adjacency matrix of $G$.  Then
$M_{ij}^k$ is equal to the number of length-$k$ walks from $v_i$ to
$v_j$.
\end{theorem}

\begin{proof}
We use induction on $k$.  The induction hypothesis is that $M_{ij}^k$
is equal to the number of length-$k$ walks from $v_i$ to $v_j$, for
all $i,j$.

Each vertex has a length-0 walk only to itself.  Since $M_{ij}^0 = 1$
if and only if $i = j$, the hypothesis holds for $k = 0$.

Now suppose that the hypothesis holds for some $k \geq 0$.  We prove
that it also holds for $k + 1$.  Every length-$(k+1)$ walk from $v_i$
to $v_j$ consists of a length $k$ walk from $v_i$ to some intermediate
vertex $v_m$ followed by an edge $\edge{v_m}{v_j}$.  Thus, the number
of length-$(k+1)$ walks from $v_i$ to $v_j$ is equal to:
\[
M_{iv_1}^k M_{{v_1}j} + 
M_{iv_2}^k M_{{v_2}j} + \ldots +
M_{iv_n}^k M_{{v_n}j}
\]
This is precisely the value of $M_{ij}^{k+1}$, so the
hypothesis holds for $k + 1$ as well.  The theorem follows by
induction.
\end{proof}


\subsection{Bipartite Graphs}

The 2-colorable graphs are important enough to merit a special name;
they are called \term{bipartite graphs}.  Suppose that $G$ is
bipartite.  Then we can color every vertex in $G$ either black or
white so that adjacent vertices get different colors.  Then we can put
all the black vertices in a clump on the left and all the white
vertices in a clump on the right.  Since every edge joins
differently-colored vertices, every edge must run between the two
clumps.  Therefore, every bipartite graph looks something like this:

\mfigure{!}{2in}{bipartite}

Bipartite graphs are both useful and common.  For example,
every path, every tree, and every even-length cycle is bipartite.

\section{Traversing a Graph}

Can you walk every hallway in the Museum of Fine Arts {\em exactly
once}?  If we represent hallways and intersections with edges and
vertices, then this reduces to a question about graphs.  For example,
could you visit every hallway exactly once in a museum with this
floorplan?

\mfigure{!}{2in}{euler-tour}

The entire field of graph theory began when Euler asked a similar
question about the seven bridges of K\"onigsberg.  In his honor, an
\term{Euler walk} is a walk that traverses every edge in a graph
exactly once.  Similarly, an \term{Euler tour} is an Euler walk that
starts and finishes at the same vertex.  Graphs with Euler tours and
Euler walks both have simple characterizations.

\begin{theorem}
A connected graph has an Euler tour if and only if every vertex has
even degree.
\end{theorem}

\begin{proof}
If a graph has an Euler tour, then every vertex must have even degree;
in particular, a vertex visited $k$ times on an Euler tour must have
degree $2k$.

Now suppose every vertex in graph $G$ has even degree.  Let $W$ be the
longest walk in $G$ that traverses every edge {\em at most} once:
\begin{eqnarray*}
W & = & v_0\ \edge{v_0}{v_1}\ v_1\ \edge{v_1}{v_2}\ v_2\ 
        \ldots\ 
        v_{n-1}\ \edge{v_{n-1}}{v_n}\ v_n
\end{eqnarray*}
The walk $W$ must traverse every edge incident to $v_n$;
otherwise, the walk could be extended.  In particular, the walk
traverses two of these edges each time it passes through $v_n$ and
traverses $\edge{v_{n-1}}{v_n}$ at the end of the walk.  This accounts
for an odd number of edges, but the degree of $v_n$ is even by
assumption.  Therefore, the walk must also begin at $v_n$; that is,
$v_0 = v_n$.

Suppose that $W$ is not an Euler tour.  Because $G$ is a connected
graph, we can find an edge not in $W$ but incident to some vertex in
$W$.  Call this edge $\edge{u}{v_i}$.  But then we can construct a
longer walk:
\[
u\ \edge{u}{v_i}\ v_i\ \edge{v_i}{v_{i+1}}\ 
\ldots\ 
\edge{v_{n-1}}{v_n}\ v_n\ \edge{v_0}{v_1}\ 
\ldots\ 
\edge{v_{i-1}}{v_i}\ v_i
\]
This contradicts the definition of $W$, so $W$ must be an
Euler tour after all.
\end{proof}

\begin{corollary}
A connected graph has an Euler walk if and only if either 0 or 2
vertices have odd degree.
\end{corollary}

A similar theorem holds for directed walks on directed graphs.

\begin{theorem}
A weakly-connected directed graph has an Euler tour if and only if the
indegree of every vertex is equal to the outdegree.
\end{theorem}

\term{Hamiltonian cycles} are the unruly cousins of Euler tours.  A
\term{Hamiltonian cycle} visits every {\em vertex} in a graph exactly
once.  There is no simple characterization of all graphs with a
Hamiltonian cycle.  In fact, determining whether a given graph has a
Hamiltonian cycle is NP-complete.

\section{Hall's Marriage Theorem}

A class contains some girls and some boys.  Each girl likes some boys
and does not like others.  Under what conditions can each girl be
paired up with a boy that she likes?

We can model the situation with a bipartite graph.  Create a vertex on
the left for each girl and a vertex on the right for each boy.  If a
girl likes a boy, put an edge between them.  For example, we might
obtain the following graph:

\mfigure{!}{2in}{hall-graph}

In graph terms, our goal is to find a \term{matching} for the girls;
that is, a subset of edges such that exactly one edge is incident to
each girl and at most one edge is incident to each boy.  For example,
here is one possible matching for the girls:

\mfigure{!}{2in}{hall-graph-matched}

Hall's Marriage Theorem states necessary and sufficient conditions for
the existence of a matching in a bipartite graph.  Hall's Theorem is a
remarkably useful mathematical tool, a hammer that bashes many
problems.  Moreover, it is the tip of a conceptual iceberg, a special
case of the ``max-flow, min-cut theorem'', which is in turn a
byproduct of ``linear programming duality'', one of the central ideas
of algorithmic theory.

We'll state and prove Hall's Theorem using girl-likes-boy terminology.
Define {\em the set of boys liked by a given set of girls} to consist
of all boys liked by at least one of those girls.  For example, the
set of boys liked by Martha and Jane consists of Tom, Michael, and
Mergatroid.

For us to have any chance at all of matching up the girls, the
following \term{marriage condition} must hold:

\bigskip
\centerline{{\em Every subset of girls likes at least as large a set of boys.}}
\bigskip

For example, we can not find a matching if some 4~girls
like only 3~boys.  Hall's Theorem says that this necessary
condition is actually sufficient; if the marriage condition holds,
then a matching exists.

\begin{theorem}
A matching for a set of girls $G$ with a set of boys $B$ can be found
if and only if the marriage condition holds.
\end{theorem}

\begin{proof}
First, let's suppose that a matching exists and show that the marriage
condition holds.  Consider an arbitrary subset of girls.  Each girl
likes at least the boy she is matched with.  Therefore, every subset
of girls likes at least as large a set of boys.  Thus, the marriage
condition holds.

Next, let's suppose that the marriage condition holds and show that a
matching exists.  We use strong induction on $\size{G}$, the number of
girls.  If $\size{G} = 1$, then the marriage condition implies that
the lone girl likes at least one boy, and so a matching exists.  Now
suppose that $\size{G} \geq 2$.  There are two possibilities:

\begin{enumerate}

\item Every proper subset of girls likes a {\em strictly larger} set of
boys.  In this case, we have some latitude: we pair an arbitrary girl
with a boy she likes and send them both away.  The marriage condition
still holds for the remaining boys and girls, so we can match the rest
of the girls by induction.

\item Some proper subset of girls $X \subset G$ likes an {\em equal-size}
set of boys $Y \subset B$.  We match the girls in $X$ with the boys in
$Y$ by induction and send them all away.  We will show that the
marriage condition holds for the remaining boys and girls, and so we
can match the rest of the girls by induction as well.

To that end, consider an arbitrary subset of the remaining girls $X'
\subseteq G - X$, and let $Y'$ be the set of remaining boys that they
like.  We must show that $\size{X'} \leq \size{Y'}$.  Originally, the
combined set of girls $X \cup X'$ liked the set of boys $Y \cup Y'$.
So, by the marriage condition, we know:
\beqn
\size{X \cup X'} & \leq & \size{Y \cup Y'}
\eeqn
We sent away $\size{X}$ girls from the set on the left (leaving $X'$)
and sent away an equal number of boys from the set on the right
(leaving $Y'$).  Therefore, it must be that $\size{X'}
\leq \size{Y'}$ as claimed.
\end{enumerate}

In both cases, there is a matching for the girls.  The theorem follows
by induction.
\end{proof}

There is an efficient algorithm for finding a matching in a bipartite
graph, if one exists.  Thus, if a problem can be reduced to finding a
matching, the problem is essentially solved from a computational
perspective.


\section{Coloring Graphs}

Each term, the MIT Schedules Office must assign a time slot for each
final exam.  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 make the exam period as short as possible.

We can recast this scheduling problem as a question about coloring the
vertices of a graph.  Create a vertex for each course with a final
exam.  Put an edge between two vertices if some student is taking both
courses.  For example, the scheduling graph might look like this:

\mfigure{!}{1.5in}{finals-uncolored}

Next, identify each time slot with a color.  For example,
Monday morning is red, Monday afternoon is blue, Tuesday morning is
green, etc.

Assigning an exam to a time slot is now equivalent to coloring the
corresponding vertex.  The main constraint is that adjacent vertices
must get different colors; otherwise, some student has two exams at
the same time.  Furthermore, in order to keep the exam period short,
we should try to color all the vertices using as few different colors
as possible.  For our example graph, three colors suffice:

\mfigure{!}{1.5in}{finals-colored}

This coloring corresponds to giving one final on Monday
morning (red), two Monday afternoon (blue), and two Tuesday morning
(green).

\subsection{k-Coloring}

Many other resource allocation problems boil down to coloring some
graph.  In general, a graph $G$ is \term{$k$-colorable} if each vertex
can be assigned one of $k$ colors so that adjacent vertices get
different colors.  The smallest sufficient number of colors is called
the \term{chromatic number} of $G$.  The chromatic number of a graph is
generally difficult to compute, but the following theorem provides an
upper bound:

\begin{theorem}
A graph with maximum degree at most $k$ is $(k+1)$-colorable.
\end{theorem}

\begin{proof}
We use induction on the number of vertices in the graph, which we
denote by $n$.  Let $P(n)$ be the proposition that an $n$-vertex graph
with maximum degree at most $k$ is $(k+1)$-colorable.  A 1-vertex
graph has maximum degree 0 and is 1-colorable, so $P(1)$ is true.

Now assume that $P(n)$ is true, and let $G$ be an $(n+1)$-vertex graph
with maximum degree at most $k$.  Remove a vertex $v$, leaving an
$n$-vertex graph $G'$.  The maximum degree of $G'$ is at most $k$, and
so $G'$ is $(k+1)$-colorable by our assumption $P(n)$.  Now add back
vertex $v$.  We can assign $v$ a color different from all adjacent
vertices, since $v$ has degree at most $k$ and $k+1$ colors are
available.  Therefore, $G$ is $(k+1)$-colorable.  The theorem follows
by induction.
\end{proof}