Chapter 11 Simple Graphs308
ChuckTomMichaelJohnAliceMarthaSaraJaneMergatroidFigure 11.9 A graph where an edge between a man and woman denotes that the
man likes the woman.
he likes? The answer, of course, depends on the bipartite graph that represents who
likes who, but the good news is that it is possible to find natural properties of the
who-likes-who graph that completely determine the answer to this question.
In general, suppose that we have a set of men and an equal-sized or larger set of
women, and there is a graph with an edge between a man and a woman if the man
likes the woman. In this scenario, the “likes” relationship need not be symmetric,
since for the time being, we will only worry about finding a mate for each man
that he likes.^5 (Later, we will consider the “likes” relationship from the female
perspective as well.) For example, we might obtain the graph in Figure 11.9.
Amatchingis defined to be an assignment of a woman to each man so that
different men are assigned to different women, and a man is always assigned a
woman that he likes. For example, one possible matching for the men is shown in
Figure 11.10.
The Matching Condition
A famous result known as Hall’s Matching Theorem gives necessary and sufficient
conditions for the existence of a matching in a bipartite graph. It turns out to be a
remarkably useful mathematical tool.
We’ll state and prove Hall’s Theorem using man-likes-woman terminology. De-
finethe set of women liked by a given set of mento consist of all women liked by
(^5) By the way, we do not mean to imply that marriage should or should not be of a heterosexual
nature. Nor do we mean to imply that men should get their choice instead of women. It’s just that
with bipartite graphs, the edges only connected male nodes to female nodes and there are fewer men
in America. So please don’t take offense.