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 girls know 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 than boys.

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 .

Now let S be a subset of and denote by and the sets of edges incident with vertices in S and ,

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.