HALL’S MARRIAGE THEOREM The bipartite graph G = (V ,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsets A of V1.
Proof:We first prove the only if part of the theorem. To do so, suppose that there is a complete matching M from V1 to V2. Then, if A ⊆ V1, for every vertex v ∈ A, there is an edge in M connecting v to a vertex in V2. Consequently, there are at least as many vertices in V2 that are neighbors of vertices in V1 as there are vertices in V1. It follows that |N(A)| ≥ |A|.
To prove the if part of the theorem, the more difficult part, we need to show that if |N(A)| ≥ |A| for all A ⊆ V1, then there is a complete matching M from V1 to V2. We will use strong induction on |V1| to prove this.
Basis step: If |V1| = 1, then V1 contains a single vertex v0. Because |N({v0})| ≥ |{v0}| = 1, there is at least one edge connecting v0 and a vertex w0 ∈ V2. Any such edge forms a complete matching from V1 to V2.
Inductive step:We first state the inductive hypothesis.
Inductive hypothesis: Let k be a positive integer. If G = (V ,E) is a bipartite graph with bipartition (V1, V2), and |V1| = j ≤ k, then there is a complete matchingM from V1 to V2 whenever the condition that |N(A)| ≥ |A| for all A ⊆ V1 is met.
Now suppose that H = (W, F) is a bipartite graph with bipartition (W1,W2) and |W1| = k 1. We will prove that the inductive holds using a proof by cases, using two case. Case (i) applies when for all integers j with 1 ≤ j ≤ k, the vertices in every set of j elements fromW1 are adjacent to at least j 1 elements ofW2. Case (ii) applies when for some j with 1 ≤ j ≤ k there is a subset W'1 of j vertices such that there are exactly j neighbors of these vertices in W2. Because either Case (i) or Case (ii) holds, we need only consider these cases to complete the inductive step.
Case (i): Suppose that for all integers j with 1 ≤ j ≤ k, the vertices in every subset of j elements from W1 are adjacent to at least j 1 elements of W2. Then, we select a vertex v ∈ W1 and an element w ∈ N({v}), which must exist by our assumption that |N({v}| ≥ |{v}| = 1. We delete v and w and all edges incident to them from H. This produces a bipartite graph H with bipartition (W1 − {v},W2 − {w}). Because |W1 − {v}| = k, the inductive hypothesis tells us there is a complete matching from W1 − {v} to W2 − {w}. Adding the edge from v to w to this complete matching produces a complete matching from W1 to W2.
Case (ii): Suppose that for some j with 1 ≤ j ≤ k, there is a subset W'1 of j vertices such that there are exactly j neighbors of these vertices in W2. Let W'2 be the set of these neighbors. Then,by the inductive hypothesis there is a complete matching from W'1 to W'2. Remove these 2j vertices from W1 and W2 and all incident edges to produce a bipartite graph K with bipartition (W1 − W'1,W2 − W'2).
We will show that the graph K satisfies the condition |N(A)| ≥ |A| for all subsets A of
W1 − W'1. If not, there would be a subset of t vertices of W1 − W'1 where 1 ≤ t ≤ k 1 − j such that the vertices in this subset have fewer than t vertices of W2 − W'2 as neighbors. Then, the set of j t vertices of W1 consisting of these t vertices together with the j vertices we removed from W1 has fewer than j t neighbors in W2, contradicting the hypothesis that |N(A)| ≥ |A| for all A ⊆ W1.
Hence, by the inductive hypothesis, the graph K has a complete matching. Combining this complete matching with the complete matching from W'1 to W'2, we obtain a complete matching from W1 to W2.
We have shown that in both cases there is a complete matching from W1 to W2. This completes the inductive step and completes the proof.
