Chapter 11 Simple Graphs406
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
Let’s look at another man/woman matching problem with an equal number of men
and women. The set up is that each person has preferences about who they would
like to marry: each man has preference list of all the women, and each woman has
a preference 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 andvice-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 who prefer one another to their spouses.
For example, suppose Brad likes Angelina best, and Angelina likes Brad best, but
Brad and Angelina are married to other people, say Jennifer and Billy Bob. Now
Brad 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.
