Mathematics for Computer Science

Chapter 11 Simple Graphs404

Inductive Step: Suppose thatjMjDmC 1  2. To find a matching forM, there
are two cases.

Case 1: Every nonempty subset of at mostmmen likes astrictly largerset of
women. In this case, we have some latitude: we pair an arbitrary man with
a woman he likes and send them both away. This leavesmmen and one
fewer women, and the matching condition will still hold. So the induction
hypothesisP.m/implies we can match the remainingmmen.

Case 2: Some nonempty subset,X, of at mostmmen likes anequal-sizeset,Y, of
women. The matching condition must hold withinX, so the strong induction
hypothesis implies we can match the men inXwith the women inY. This
leaves the problem of matching the setMXof men to the setWY of
women.
But the problem of matchingMXagainstWYalso satisfies the Match-
ing condition, because any subset of men inMXwho liked fewer women
inWYwould imply there was a set of men who liked fewer women in the
whole setW. Namely, if a subsetM 0 MXliked only a strictly smaller
subset of womenW 0 WY, then the setM 0 [Xof men would like only
women in the strictly smaller setW 0 [Y. So again the strong induction hy-
pothesis implies we can match the men inMXwith the women inWY,
which completes a matching forM.

So in both cases, there is a matching for the men, which completes the proof of
the Inductive step. The theorem follows by induction. 

The proof of Theorem 11.5.2 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 per-
spective.

A Formal Statement

Let’s restate Theorem 11.5.2 in abstract terms so that you’ll not always be con-
demned to saying, “Now this group of men likes at least as many women... ”

Definition 11.5.3.Amatchingin a graphGis a setMof edges ofGsuch that no
vertex is an endpoint of more than one edge inM. A matching is said tocover a
set,S, of vertices iff each vertex inSis an endpoint of an edge of the matching. A
matching is said to beperfect if it coversV.G/. In any graph,G, the set N.S/of