Hall’s Theorem by Induction

Hall’s Theorem and Its Induction Structure

Hall’s theorem turns a condition on every group of left-side vertices into a guarantee that all left-side vertices can be paired with distinct neighbors. Its induction proof hinges on a useful distinction: sometimes a proper group has exactly enough neighbors, allowing the problem to split cleanly; otherwise every proper group has extra room, so one pair can be chosen and removed.

Throughout, \(G=(X\cup Y,E)\) is a finite simple bipartite graph with parts \(X\) and \(Y\). For \(S\subseteq X\), its neighborhood is \(N(S)=\{y\in Y: xy\in E\text{ for some }x\in S\}\). A matching is a set of edges no two of which share an endpoint. It saturates \(X\) if every vertex in \(X\) is incident to one of its edges; vertices in \(Y\) need not all be matched.

Proof. First suppose a matching saturates \(X\). For any \(S\subseteq X\), the matching pairs each vertex of \(S\) with a neighbor in \(N(S)\). Those neighbors are distinct because the edges form a matching. Thus \(|N(S)|\ge |S|\). This also holds for \(S=\varnothing\), since both cardinalities are zero.

For the converse, we prove by induction on \(n=|X|\) that Hall’s condition guarantees a matching saturating \(X\). If \(n=0\), the empty set of edges is a matching saturating \(X\). If \(n=1\), write \(X=\{x\}\). Hall’s condition for \(\{x\}\) gives \(|N(\{x\})|\ge1\), so some edge \(xy\) exists; that single edge saturates \(X\).

Now let \(n\ge2\), and assume the claim holds for every bipartite graph whose left side has fewer than \(n\) vertices. There are two cases.

Case 1: a proper nonempty tight subset exists. Suppose \(S\) is a nonempty proper subset of \(X\) with \(|N(S)|=|S|\). Consider first the bipartite graph with left side \(S\), right side \(N(S)\), and all edges of \(G\) between them. For every \(A\subseteq S\), its neighborhood in this graph is \(N(A)\), since \(N(A)\subseteq N(S)\). Hall’s condition therefore holds on \(S\). As \(|S|<n\), induction gives a matching saturating \(S\).

Next consider the graph with left side \(X\setminus S\), right side \(Y\setminus N(S)\), and all edges of \(G\) between these sides. For \(T\subseteq X\setminus S\), its neighborhood in this graph is \(N(T)\setminus N(S)\). The sets \(N(S)\) and \(N(T)\setminus N(S)\) are disjoint, and their union is \(N(S\cup T)\). Hall’s condition in \(G\) gives

Since \(|N(S)|=|S|\), subtracting \(|S|\) yields \(|N(T)\setminus N(S)|\ge|T|\). This holds for every such \(T\), including \(T=\varnothing\). Hall’s condition holds on the second smaller graph, so induction gives a matching saturating \(X\setminus S\). The two matchings use disjoint left sides and disjoint right sides: the first uses right vertices in \(N(S)\), and the second uses right vertices in \(Y\setminus N(S)\). Their union is therefore a matching saturating \(X\).

Case 2: no proper nonempty tight subset exists. For every nonempty proper \(T\subset X\), Hall’s condition holds and equality does not, so the integer cardinalities satisfy \(|N(T)|\ge |T|+1\). Choose any \(x\in X\). Hall’s condition for \(\{x\}\) gives a neighbor \(y\in Y\). Delete \(x\) and \(y\), keeping the edges between the remaining vertices. If \(T\subseteq X\setminus\{x\}\) is empty, its neighborhood has size zero. If \(T\) is nonempty, it is a proper subset of \(X\), so \(|N(T)|\ge |T|+1\). Removing \(y\) can remove at most one vertex from \(N(T)\), and hence the neighborhood remaining in \(Y\setminus\{y\}\) has size at least \(|T|\). The smaller graph satisfies Hall’s condition. By induction it has a matching saturating \(X\setminus\{x\}\). Adding the edge \(xy\) gives a matching saturating \(X\), because \(x\) and \(y\) were deleted from the smaller graph. Both cases complete the induction and the proof. \(\square\)

Using a Tight Subset to Split the Problem

A tight subset is one for which the number of available neighbors equals the number of left-side vertices. In the proof, the tight subset and its neighborhood form one smaller problem. The remaining left-side vertices must be matched outside that neighborhood, and Hall’s condition guarantees enough neighbors there too. The disjoint right-side regions are what allow the two smaller matchings to be combined.

When Every Proper Subset Has Extra Neighbors

If there is no proper nonempty tight subset, every such subset has at least one more neighbor than its size. The proof uses that extra neighbor-count as a one-vertex allowance: after choosing an edge \(xy\), deleting \(y\) can reduce any remaining neighborhood by at most one. The empty subset causes no difficulty, and the induction is applied only after the graph has fewer left-side vertices.

Unequal Part Sizes and the Scope of the Conclusion

Hall’s condition is imposed on subsets of \(X\), because the goal is to saturate \(X\). It does not require \(|X|=|Y|\), and it does not promise that every vertex of \(Y\) is matched. For instance, a graph can satisfy Hall’s condition on a smaller left side while leaving some right-side vertices unused.

Common Pitfalls and Why the Proof Works

A frequent error in the strict-inequality case is to say that deleting a right-side vertex cannot hurt Hall’s condition. It can: a neighborhood may lose that vertex. The valid argument is that each nonempty remaining left subset was a proper subset of the original \(X\), so it had at least one extra neighbor before deletion. Losing at most one still leaves enough.

For a concrete calculation, use the strict-case graph above and choose \(a2\). Before deletion, \(N(\{b\})=\{2,3\}\), of size \(2\). After deleting \(2\), the neighborhood is \(\{3\}\), of size \(1\). The incorrect claim that its size is unchanged would give \(2\); the correct count is \(2-1=1=|\{b\}|\), which is exactly enough for Hall’s condition.

A second error is to use \(N(T)\) itself as the right-side neighborhood in the residual graph of the tight-subset case. The vertices in \(N(S)\) are not available there. The correct residual neighborhood is \(N(T)\setminus N(S)\), and its size is controlled by applying Hall’s condition to \(S\cup T\) and using \(|N(S)|=|S|\).

The two cases cover all possibilities for \(n\ge2\): either a proper nonempty subset is tight, or none is. The base cases ensure that induction does not rely on choosing a vertex or a neighbor when none can be guaranteed. This proof is useful because it explains not only that Hall’s condition suffices, but why tight subsets permit a split while strict inequalities permit a deletion.