SKEDSOFT

Graph Theory

HALL’S MARRIAGE THEOREM : If G is a bipartite graph with bipartition sets V1 and V2, then there exists a matching which saturates V1 if and only if, for every subset X of V1, | X | ≤ | A(X) |.

Proof. It remains to prove that the given condition is sufficient, so we assume that | X | ≤ | A(X) | for all subsets X of V1.
In particular, this means that every vertex in V1 is joined to at least one vertex in V2 and also that
| V1 | ≤ | V2 |.
Assume that there is no matching which saturates all vertices of V1. We derive a contradiction.

We turn G into a directed network in exactly the same manner as with the job assignment application. Specifically, we adjoin two vertices s and t to G and draw directed arcs from s to each vertex in V1 and from each vertex in V2 to t. Assign a weight of 1 to each of these new arcs. Orient each edge of G from its vertex in V1 to its vertex in V2, and assign a large integer I > | V1 | to each of these edges.

As noted before, there is a one-to-one correspondence between matchings of G and (s, t)-flows in this network, and the value of the flow equals the number of edges in the matching.

Since we are assuming that there is no matching which saturates V1, it follows that every flow has value less than | V1 | and hence by Max-Flow-Mincut theorem, there exists an (s, t)-cut
{S, T} {s ∈ S, t ∈ T).
Whose capacity is less than | V1 |.
Now every original edge of G has been given a weight larger than | V1 |. Since the capacity of our cut is less than | V1 |, no edge of G can join a vertex of S to a vertex of T.
Letting X = V1 ∩ S, we have A(X) ⊆ S.
Since each vertex in A(X) is joined to t ∈ T, each such vertex contributes 1 to the capacity of the cut.
Similarly, since s is joined to each vertex in V1\X, each such vertex contributes 1. Since
| X | ≤ | A(X) |, we have a contradiction to the fact that the capacity is less than | V1 |.

Problem. Let G be a bipartite graph with bipartition sets v1, v2 in which every vertex has the same degree k. Show that G has a matching which saturates v1.
Solution. Let X be any subset of v1 and let A(X) be as defined earlier. We count the number of edges joining vertices of X to vertices of A(X).
On the one hand (thinking of X), this number is k | X |.
On the otherhand (thinking of A(X)), this number is atmost k | A(X) | since k | A(X) | is the total degree of all vertices in A(X).
Hence, k | X | ≤ k | A(X) |, so | X | ≤ | A(X) |.