Hall's Marriage Theorem - Proof of The Graph Theoretic Version

Proof of The Graph Theoretic Version

We first prove: If a bipartite graph G = (X + Y, E) = G(X, Y) has an X-saturating matching, then |N_G(W)| ≥ |W| for all W ⊆ X.

Suppose M is a matching that saturates every vertex of X. Let the set of all vertices in Y matched by M to a given W be denoted as M(W). Therefore, |M(W)|=|W|, by the definition of matching. But M(W) ⊆ N_G(W), since all elements of M(W) are neighbours of W. So, |N_G(W)| ≥ |M(W)| and hence, |N_G(W)| ≥ |W|.

Now we prove: If |N_G(W)| ≥ |W| for all W ⊆ X, then G(X,Y) has a matching that saturates every vertex in X.

Assume for contradiction that G(X,Y) is a bipartite graph that has no matching that saturates all vertices of X. Let M be a maximum matching, and u a vertex not saturated by M. Consider all augmenting paths (i.e., paths in G alternately using edges outside and inside M) starting from u. Let the set of all points in Y connected to u by these augmenting paths be T, and the set of all points in X connected to u by these augmenting paths (including u itself) be W. No maximal augmenting path can end in a vertex in Y, lest we could augment M to a strictly larger matching. Thus every vertex in T is matched by M to a vertex in W. Conversely, every vertex v in W \ {u} is matched by M to a vertex in T (namely, the vertex preceding v on an augmenting path ending at v). Thus, M provides a bijection of W \ {u} and T, which implies |W| = |T| + 1. On the other hand, N_G(W) ⊆ T: let v in Y be connected to a vertex w in W. If the edge (w,v) is in M, then v is in T by the previous part of the proof, otherwise we can take an augmenting path ending in w and extend it with v, showing that v is in T. Hence, |N_G(W)| = |T| = |W| − 1, a contradiction.