Hall’s Theorem Through Augmenting Paths

From Matchings to Hall’s Condition

Hall’s theorem connects a local counting condition to the existence of a matching that covers an entire side of a bipartite graph. The augmenting-path proof makes the connection constructive: if a maximum matching leaves a left vertex uncovered, following alternating edges from that vertex produces a set of left vertices with too few neighbors.

Throughout, \(G=(L\cup R,E)\) is a finite simple bipartite graph with disjoint parts \(L\) and \(R\); every edge has one endpoint in each part. For \(S\subseteq L\), its neighborhood is \(N(S)=\{r\in R: \ell r\in E\text{ for some }\ell\in S\}\). A matching is a set of edges with no shared endpoints. It saturates \(L\) if every vertex in \(L\) is incident to one of its edges.

An augmenting path starts and ends with edges outside \(M\), so it contains one more edge outside \(M\) than inside it. After the replacement, every internal vertex is still incident to exactly one selected edge, while each endpoint becomes matched. Thus the new set is a matching with one more edge.

The theorem’s condition concerns every subset of the left side, not just the whole side. If \(S\) has \(k\) vertices and fewer than \(k\) neighbors, distinct representatives for all vertices of \(S\) are impossible: each would need a different neighbor in \(N(S)\).

Why the Absence of an Augmenting Path Matters

Proof. If there is an augmenting path, changing the edges of \(M\) along it gives a matching with one more edge, so \(M\) is not maximum. Conversely, suppose \(M\) is not maximum. Choose a matching \(M'\) with \(|M'|>|M|\), and consider the graph consisting of the edges that belong to exactly one of \(M\) and \(M'\). At each vertex there is at most one incident edge from each matching, so every vertex has degree at most two in this graph. Each of its components is therefore an isolated vertex, a path, or a cycle. Along every nontrivial component the edges alternate between \(M\) and \(M'\), since two consecutive edges cannot belong to the same matching. An alternating cycle has equally many edges from each matching. An alternating path has either equal numbers or one more edge from one matching than the other. Because \(M'\) has more edges in total, some component has more \(M'\)-edges than \(M\)-edges. That component must be a path beginning and ending with \(M'\)-edges. Its endpoints have no incident \(M\)-edge in the component, and they have no other incident \(M\)-edge outside it: any such edge would also belong to the graph under consideration and would extend the component. Hence both endpoints are unmatched by \(M\). The path is an augmenting path for \(M\), proving the converse. \(\square\)

This lemma lets us use a maximum matching as a certificate that no augmenting path remains. Since the graph is finite, a maximum matching exists: among the finitely many subsets of \(E\), at least one matching has largest size.

Hall’s Theorem by Alternating Reachability

Proof. First suppose a matching \(M\) saturates \(L\). For any \(S\subseteq L\), the matching edges incident to vertices in \(S\) have distinct endpoints in \(R\), all belonging to \(N(S)\). There are \(|S|\) such endpoints, so \(|N(S)|\ge |S|\). This also holds for \(S=\varnothing\), since both sizes are zero.

For the converse, suppose the condition holds, and choose a maximum matching \(M\). Assume, seeking a contradiction, that \(M\) does not saturate \(L\). Choose an unmatched vertex \(\ell_0\in L\). Direct every edge outside \(M\) from \(L\) to \(R\), and every edge in \(M\) from \(R\) to \(L\). Let \(S\subseteq L\) and \(T\subseteq R\) be the vertices reachable from \(\ell_0\) by following these directions, including \(\ell_0\) in \(S\).

No vertex of \(T\) can be unmatched by \(M\). If one were, a directed path from \(\ell_0\) to it would be an alternating path with unmatched endpoints, hence an augmenting path. That contradicts the maximality of \(M\), by the lemma.

We now show \(N(S)=T\). Every vertex of \(T\) is reached across an edge from a vertex of \(S\), so \(T\subseteq N(S)\). For the reverse inclusion, take \(\ell\in S\) and an edge \(\ell r\). If \(\ell r\notin M\), the directed edge goes from \(\ell\) to \(r\), so \(r\in T\). If \(\ell r\in M\), then \(\ell\ne\ell_0\), because \(\ell_0\) is unmatched. Every reached left vertex other than \(\ell_0\) was reached from its matched partner, so \(r\in T\) in this case as well. Thus every neighbor of \(S\) is in \(T\), proving equality.

Every vertex of \(T\) is matched, and its matched partner is in \(S\), because the matched edge is directed from \(T\) to \(S\). Conversely, every vertex of \(S\setminus\{\ell_0\}\) was reached along its matched edge from a vertex of \(T\). These matched edges pair \(T\) bijectively with \(S\setminus\{\ell_0\}\). Therefore \[ |N(S)|=|T|=|S|-1<|S|, \] contradicting the assumed condition for this subset \(S\). The contradiction shows that \(M\) saturates \(L\). If \(L\) is empty, the empty matching already saturates it, so the conclusion holds in that case too. \(\square\)

Worked Examples

Using the Proof as a Procedure

The converse proof also explains how to search for a matching. Start with any matching. From an unmatched left vertex, follow edges outside the matching from left to right, and matched edges from right to left. If an unmatched right vertex is reached, the path to it is augmenting; flip the matched and unmatched edges along that path. If no unmatched right vertex is reached, the reachable left set \(S\) and right set \(T\) satisfy \(N(S)=T\) and \(|T|=|S|-1\), giving an explicit failure of Hall’s condition.

Each augmentation increases the matching size by one, and a matching has at most \(|L|\) edges. Thus the process cannot augment more than \(|L|\) times. If Hall’s condition holds, the theorem proves that a maximum matching saturates \(L\); if the process stops without saturation, the reachable set certifies a violation. The proof therefore gives both a matching when the condition succeeds and a specific obstructing subset when it fails.

A Common Mistake

Having enough vertices on the right is not enough. For example, let \(L=\{a,b,c\}\), \(R=\{1,2,3\}\), and \(E=\{a1,b1,c1\}\). Although \(|R|=|L|=3\), every left vertex has the same sole neighbor. For \(S=L\), the correct calculation is \(N(S)=\{1\}\), so \(|N(S)|=1<3=|S|\). A matching can contain only one edge.

A related error is stopping the reachability search after finding the neighbors of the starting vertex. In the example with edges \(px,qx,ry\), the starting vertex \(p\) first reaches \(x\), but the matched edge from \(x\) then reaches \(q\). The relevant set is \(S=\{p,q\}\), not just \(\{p\}\). Following both directions of the alternating search is what exposes the shortage \(|N(S)|=1<2=|S|\).