9.2. Matching in bipartite graphs.
Given a family of subset of a set X. Can we find m
distinct elements of X, one from each
?
A set with these properties
is called a set of distinct
representatives of the family A.
The set system A is naturally identifiable with a bipartite
graph with vertex classes and
in which
is joined to every
contained in
.
A system of distinct representatives is
then a set of independent edges. We also say that there is a complete matching
from to
.
Reformulation of the problem: given m girls and n boys. Under what condition can we marry off all the girls provided we do not want to carry matchmaking as far as to marry a girl to a boy she does not even know?
If there are k girls who altogether know at
most boys then we cannot find suitable marriages
for the girls.
If there is a complete matching from to
then for every
there are at least
vertices of
adjacent to a vertex in S, that is
Theorem 9.5. (Hall's theorem): A bipartite graph G with vertex set and
contains a complete matching from
to
iff
for every
Proof.
We have already seen that the condition is necessary so we have to prove only the sufficiency.
We shall apply induction on m, the number of girls.
-
For
the conditionis is clearly sufficient.
-
Suppose that
and the statement of the theorem is valid for each l smaller than m.
- Suppose first that any k girlsknow at least
boys. Then we arrange one marriage arbitrary. The remaining sets of girls and boys still satisfy the condition, so the other
girls can be married off by induction.
- Suppose now that for some k, there are k girls who altogether know exactly k boys. These girls can be married off by induction.
- What about the other girls?
- We can marry them off if they satisfy the condition (we do not count the boys who are already married).
- But the condition is satisfied since if some l girls to be married know fewer then l remaining boys then these girls together with the first k girls would know fewer thanboys.

Corollary 9.6..: If G is a k-regular
bipartite graph with then G has
a perfect matching.
Proof.
Let G be
a k-regular bipartite graph with bipartition . Since G is k-regular, so
and so, since
.




respectively.
By definition of and therefore
.
So, it
follows that .
Let us use the Hall's Theorem (8.3): G
has perfect matching M from to
.
Since so we get that M is a perfect matching.