Chapter 11 Simple Graphs312
It follows thatdjN.S/j djSj. Cancellingdcompletes the derivation of equa-
tion (11.2).
Regular graphs are a large class of degree-constrained graphs that often arise in
practice. Hence, we can use Theorem 11.5.6 to prove that every regular bipartite
graph has a perfect matching. This turns out to be a surprisingly useful result in
computer science.
Definition 11.5.7.A graph is said to beregularif every node has the same degree.
Theorem 11.5.8.Every regular bipartite graph has a perfect matching.
Proof. LetGbe a regular bipartite graph. Since regular graphs are degree-constrained,
we know by Theorem 11.5.6 that there must be a matching inGthat coversL.G/.
Such a matching is only possible whenjL.G/j jR.G/j. ButGis also degree-
constrained if the roles ofL.G/andR.G/are switched, which implies thatjR.G/j
jL.G/jalso. That is,L.G/andR.G/are the same size, and any matching covering
L.G/will also coverR.G/. So every node inGis an endpoint of an edge in the
matching, and thusGhas a perfect matching.
11.6 The Stable Marriage Problem
We next consider a version of the bipartite matching problem where there are an
equal number of men and women, and where each person has preferences about
who they would like to marry. In fact, we assume that each man has a complete list
of all the women ranked according to his preferences, with no ties. Likewise, each
woman has a ranked list of all of the men.
The preferences don’t have to be symmetric. That is, Jennifer might like Brad
best, but Brad doesn’t necessarily like Jennifer best. The goal is to marry everyone:
every man must marry exactly one woman and vice-versa—no polygamy. More-
over, we would like to find a matching between men and women that isstablein
the sense that there is no pair of people that prefer each other to their spouses.
For example, supposeeveryman likes Angelina best, and every woman likes
Brad best, but Brad and Angelina are married to other people, say Jennifer and Billy
Bob. NowBrad and Angelina prefer each other to their spouses, which puts their
marriages at risk: pretty soon, they’re likely to start spending late nights together
working on problem sets!
This unfortunate situation is illustrated in Figure 11.11, where the digits “1”
and “2” near a man shows which of the two women he ranks first and second,
respectively, and similarly for the women.
