\hyperdef{bipartite}{matching}{\section{Bipartite Matchings}}

\subsection{Bipartite Graphs}\label{bipartitesec}

There were two kinds of vertices in the ``Sex in America'' graph ---males
and females, and edges only went between the two kinds.  Graphs like this
come up so frequently they have earned a special name ---they are called
\term{bipartite graphs}.

\begin{definition}
A \emph{bipartite graph} is a graph together with a partition of its
vertices into two sets, $L$ and $R$, such that every edge is incident to a
vertex in $L$ and to a vertex in $R$.
\end{definition}

So every bipartite graph looks something like this:

\mfigure{!}{2in}{figures/bipartite.pdf}

Now we can immediately see how to color a bipartite graph using only two
colors: let all the $L$ vertices be black and all the $R$ vertices be
white.  Conversely, if a graph is 2-colorable, then it is bipartite with
$L$ being the vertices of one color and $R$ the vertices of the other
color.  In other words,
\begin{quote}
``bipartite'' is a synonym for ``2-colorable.''
\end{quote}

The following Lemma gives another useful characterization of bipartite
graphs.
\hyperdef{odd}{cycle}
{\begin{theorem}\label{odd-cycle}
A graph is bipartite iff it has no odd-length cycle.
\end{theorem}}

%The proof of Theorem~\ref{odd-cycle} will be on a problem set.

\begin{notesproblem}{}
Prove Theorem~\ref{odd-cycle}
\end{notesproblem}

\subsection{Bipartite Matchings}

The \emph{bipartite matching problem} resembles the stable Marriage
Problem in that it concerns a set of girls and a set of at least as many
boys.  There are no preference lists, but each girl does have some boys
she likes and others she does not like.  In the bipartite matching
problem, we ask whether every girl can be paired up with a boy that she
likes.

Any particular matching problem can be specified by a bipartite graph with
a vertex for each girl, a vertex for each boy, and an edge between a boy
and a girl iff the girl likes the boy.  For example, we might obtain the
following graph:

\mfigure{!}{2in}{figures/hall-graph.pdf}

Now a \emph{matching} will mean a way of assigning every girl to a boy so
that different girls are assigned to different boys, and a girl is always
assigned to a boy she likes.  For example, here is one possible matching
for the girls:

\mfigure{!}{2in}{figures/hall-graph-matched.pdf}

Hall's Matching Theorem states necessary and sufficient conditions for the
existence of a matching in a bipartite graph.  It turns out to be a
remarkably useful mathematical tool.  \iffalse , 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.  \fi

\subsection{The Matching Condition}

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{matching 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 matching 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 matching condition holds.
\end{theorem}

\begin{proof}
First, let's suppose that a matching exists and show that the matching
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 matching condition
holds.

Next, let's suppose that the matching condition holds and show that a
matching exists.  We use strong induction on $\card{G}$, the number of
girls.  If $\card{G} = 1$, then the matching condition implies that the
lone girl likes at least one boy, and so a matching exists.  Now suppose
that $\card{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 matching 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
matching 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 $\card{X'} \leq \card{Y'}$.  Originally, the
combined set of girls $X \cup X'$ liked the set of boys $Y \cup Y'$.
So, by the matching condition, we know:
%
\[
\card{X \cup X'}  \leq  \card{Y \cup Y'}
\]
%
We sent away $\card{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 $\card{X'}
\leq \card{Y'}$ as claimed.

\end{enumerate}

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

The proof of this theorem gives an algorithm for finding a matching in
a bipartite graph, albeit not a very efficient one.  However,
efficient algorithms for finding a matching in a bipartite graph do
exist.  Thus, if a problem can be reduced to finding a matching, the
problem is essentially solved from a computational perspective.

\subsection{A Formal Statement}

Let's restate Hall's Theorem in abstract terms so that you'll not
always be condemned to saying, ``Now this group of little girls likes
at least as many little boys...''  

% A \emph{matching} in a graph is an injection on the set of vertices
% that only maps a vertex to an adjacent vertex.  Albert: Do you mean
% in the bipartite case?  Otherwise, wouldn't the injection
% f(i)->i+1(mod n) on {1,..,n} determine the cycle C_n and an
% injection?

% Also, is it true that, in this class, an injection/function on $L$
% need only have a domain that is a subset of $L$?  If not I'll need
% to modify the next paragraph.
%

% % CLIFF: Thanks for your correction.  My def with injections (which indeed
% % may be partial) was a failed attempt to be slick.  But given that it's
% % wrong, there's no point in hanging onto injections, so I've revised as
% % follows:

A \emph{matching} in a graph, $G$, is a set of edges such that no two
edges in the set share a vertex.  A matching is said to \emph{cover} a
set, $L$, of vertices iff each vertex in $L$ has an edge of the matching
incident to it.

In any graph, the set $N(S)$, of \emph{neighbors}\footnote{An equivalent
  definition of $N(S)$ uses relational notation: $N(S)$ is simply the
  image, $SR$, of $S$ under the adjacency relation, $R$, on vertices of
  the graph.} of some set, $S$, of vertices is the set of all vertices
adjacent to some vertex in $S$.  That is,
\[
N(S) \eqdef \set{r \suchthat \edge{s}{r}\text{ is an edge for some }s \in S}.
\]

$S$ is called a \emph{bottleneck} if
\[
\card{S} > \card{N(S)}.
\]

\begin{theorem}[Hall's Theorem]
  Let $G$ be a bipartite graph with vertex partition $L,R$.  There is
  matching in $G$ that covers $L$ iff no subset of $L$ is a bottleneck.
\end{theorem}

\subsubsection{An Easy Matching Condition}

The bipartite matching condition requires that \emph{every} subset of
girls has a certain property.  In general, verifying that every subset has
some property, even if it's easy to check any particular subset for the
property, quickly becomes overwhelming because the number of subsets of
even relatively small sets is enormous ---over a billion subsets for a set
of size 30.

However, there is a simple property of vertex degrees in a bipartite graph
that guarantees a match and is very easy to check.  Namely, call a
bipartite graph \emph{degree-constrained} if vertex degrees on the left
are at least as large as those on the right.  More precisely,

\hyperdef{degree}{constrained}{
\begin{definition}
A bipartite graph $G$ with vertex partition $L,R$ is
\emph{degree-constrained} if $\degr{l} \geq \degr{r}$ for every $l \in L$
and $r \in R$.
\end{definition}}

Now we can always find a matching in a degree-constrained bipartite graph.

\begin{lemma}
Every degree-constrained bipartite graph satisifies the matching condition.
\end{lemma}

\begin{proof}
Let $S$ be any set of vertices in $L$.  The number of edges incident to
vertices in $S$ is exactly the sum of the degrees of the vertices in $S$.
Each of these edges is incident to a vertex in $N(S)$ by definition of
$N(S)$.  So the sum of the degrees of the vertices in $N(S)$ is at least
as large as the sum for $S$.  But since the degree of every vertex in
$N(S)$ is at most as large as the degree of every vertex in $S$, there
would have to be at least as many terms in the sum for $N(S)$ as in the
sum for $S$.  So there have to be at least as many vertices in $N(S)$ as
in $S$, proving that $S$ is not a bottleneck.  So there are no
bottlenecks, proving that the degree-constrained graph satisifies the
matching condition.
\end{proof}

Of course being degree-constrained is a very strong property, and lots of
graphs that aren't degree-constrained have matchings.  But we'll see
examples of degree-constrained graphs come up naturally in some later
applications.


\endinput