11.5. Bipartite Graphs & Matchings 311
neighborsof some setSof vertices is the image ofSunder the edge-relation, that
is,
N.S/WWDfrjhs—ri 2 E.G/for somes 2 Sg:
Sis called abottleneckif
jSj>jN.S/j:
Theorem 11.5.4(Hall’s Theorem).LetGbe a bipartite graph. There is a matching
inGthat coversL.G/iff no subset ofL.G/is a bottleneck.
An Easy Matching Condition
The bipartite matching condition requires thateverysubset of men 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 the existence of a matching. Namely,
call a bipartite graphdegree-constrainedif vertex degrees on the left are at least as
large as those on the right. More precisely,
Definition 11.5.5.A bipartite graphGisdegree-constrainedwhen deg.l/deg.r/
for everyl 2 L.G/andr 2 R.G/.
For example, the graph in Figure 11.9 is degree-constrained since every node on
the left is adjacent to at least two nodes on the right while every node on the right
is adjacent to at most two nodes on the left.
Theorem 11.5.6. IfGis a degree-constrained bipartite graph, then there is a
matching that coversL.G/.
Proof. We will show thatGsatisfies Hall’s condition, namely, ifSis an arbitrary
subset ofL.G/, then
jN.S/jjSj: (11.2)
SinceGis degree-constrained, there is ad > 0such that deg.l/d deg.r/
for everyl 2 Landr 2 R. Since every edge with an endpoint inShas its other
endpoint inN.S/by definition, and every node inN.S/is incident to at mostd
edges, we know that
djN.S/j#edges with an endpoint inS:Also, since every node inSis the endpoint of at leastdedges,
#edges incident to a vertex inSdjSj: