Bipartite matchings and Hall's theorem

A bipartite graph has disjoint vertex classes $L$ and $R$, with every edge joining one class to the other. A matching is a set of edges with no shared endpoints. It saturates $L$ if every vertex of $L$ belongs to a selected edge. Saturation need not cover all of $R$ when the classes have different sizes. A perfect matching covers both classes. These distinctions matter in applications with more available slots than applicants.

For a subset $S\subseteq L$, let $N(S)$ be the union of all its neighbors in $R$. If a matching saturates $L$, its edges must send the distinct vertices of $S$ to distinct members of $N(S)$. Hence $|N(S)|\ge|S|$ for every such subset. Checking only individual vertices misses bottlenecks: three applicants may each have two choices while all three share the same two slots. The failure is visible only after grouping the competing applicants.

Hall's theorem states that a finite bipartite graph has a matching saturating $L$ if and only if this neighbor inequality holds for every subset of $L$. Necessity is the assignment count just given. For the sufficiency idea, choose a maximum matching and suppose some left vertex is unmatched. Search from it by alternating unmatched edges from left to right and matched edges from right to left. If an unmatched right vertex is reached, flipping the path increases the matching, contradicting maximum size.

If no unmatched right vertex is reached, let $S$ be the reached left vertices and $T$ the reached right vertices. Every neighbor of $S$ lies in $T$: nonmatching edges are explored, and the matching partner of a reached matched left vertex was already reached. Every vertex in $T$ is matched back into $S$, while the starting left vertex is unmatched. Thus $|T|=|S|-1$, contradicting Hall because $T=N(S)$. This argument proves sufficiency and explains how a failed search produces a concrete shortage certificate.

An augmenting path begins and ends at unmatched vertices and alternates between edges outside and inside the current matching. Flipping membership along it adds one more unmatched edge than it removes, increasing the matching size by one while preserving the endpoint constraint. An early choice need not be permanent: a chain of reassigned slots can free a desirable slot for a previously unmatched applicant. A greedy procedure that never revisits choices can stop too soon.

A maximal matching cannot be enlarged by simply adding one edge, but a maximum matching has the greatest possible size among all matchings. The first is a local property and the second is global. In a three-edge path, selecting the middle edge is maximal, yet the two outside edges form a larger matching. Hall's theorem is an existence criterion; augmenting paths provide a constructive improvement mechanism. When eligibility has capacities or weights, those must be added to the model rather than silently changing the meaning of a matching.