From a Maximum Matching to a Deficient Set
Hall’s condition asks whether every subset of the left side of a bipartite graph has at least as many neighbors as vertices. When a maximum matching fails to cover the left side, one can find a specific subset that violates this condition. The construction is a search that follows unmatched edges from left to right and matched edges from right to left. The reachable vertices on the left form the certificate.
Throughout, \(G=(X\cup Y,E)\) is a finite simple bipartite graph: \(X\) and \(Y\) are disjoint vertex sets, and every edge has one endpoint in each set. A matching \(M\subseteq E\) is a set of edges with no shared endpoints. A vertex is saturated by \(M\) if it is incident to an edge of \(M\). A matching is maximum if no matching in \(G\) has more edges. For \(S\subseteq X\), its neighborhood \(N(S)\subseteq Y\) consists of all vertices adjacent to at least one vertex of \(S\).
Now fix a maximum matching \(M\) that does not saturate \(X\). Start from every unmatched vertex in \(X\). From a vertex in \(X\), follow edges not in \(M\) toward \(Y\); from a vertex in \(Y\), follow its edge in \(M\), if it has one, toward \(X\). These alternating steps define the search. Write \(S\) for the reached vertices in \(X\) and \(T\) for the reached vertices in \(Y\).
Why the Search Produces a Certificate
Proof. Suppose such a path exists. Its edges alternate between edges outside \(M\) and edges in \(M\), with the first and last edges outside \(M\), since both endpoints are unmatched. Therefore it contains one more edge outside \(M\) than inside \(M\). Remove from \(M\) the path edges that belong to \(M\), and add the path edges that do not belong to \(M\). At each internal path vertex, one incident matching edge is replaced by the other path edge; the endpoints gain an incident edge. Vertices not on the path are unchanged, so the result is a matching with one more edge than \(M\). This contradicts the maximal size of \(M\). \(\square\)
Proof. Let \(U\) be the set of unmatched vertices of \(X\). By assumption, \(U\ne\varnothing\), and every vertex of \(U\) is included among the search’s starting vertices. Every reached vertex of \(Y\) was reached from a vertex in \(S\) along an edge not in \(M\), so \(T\subseteq N(S)\).
For the reverse inclusion, let \(x\in S\) and let \(y\) be any neighbor of \(x\). If \(xy\notin M\), the search follows that edge from \(x\) to \(y\), so \(y\in T\). If \(xy\in M\), then \(x\notin U\), because vertices in \(U\) are unmatched. A reached vertex of \(X\) that is not a starting vertex can only have been reached by following its matching edge from \(Y\). Thus \(y\) was already reached, and again \(y\in T\). This proves \(N(S)\subseteq T\), hence \(T=N(S)\).
No vertex of \(T\) can be unmatched: the search would then give an alternating path from an unmatched vertex in \(U\) to an unmatched vertex of \(Y\), contrary to the lemma. Every vertex of \(T\) is therefore matched, and its matching partner lies in \(S\), since the search follows matching edges from \(Y\) to \(X\). Conversely, every vertex of \(S\setminus U\) is reached by such a matching edge, so its matching partner lies in \(T\). Matching edges give a one-to-one correspondence between \(T\) and \(S\setminus U\). Consequently, \(|T|=|S\setminus U|\), while \(S\) is the disjoint union of \(S\setminus U\) and \(U\). Since \(U\ne\varnothing\), \(|S|=|T|+|U|>|T|\). Together with \(T=N(S)\), this is the required deficiency. \(\square\)
The Search Procedure
The search can be carried out by breadth-first search, using a queue. Mark all unmatched vertices in \(X\) as reached and put them in the queue. When processing a reached \(X\)-vertex, inspect its incident edges outside \(M\) and add any new \(Y\)-endpoints to the queue. When processing a reached \(Y\)-vertex, follow its matching edge, if it has one, and add its \(X\)-endpoint if it is new. Stop when the queue is empty. The reached vertices on the two sides are \(S\) and \(T\).
Put every unmatched vertex of \(X\) into the queue and mark it reached.
For each reached \(x\in X\), add every unreached neighbor \(y\in Y\) for which \(xy\notin M\).
For each reached \(y\in Y\), add its matching partner if \(y\) is matched and that partner is not yet reached.
When no vertices remain in the queue, output \(S\), the reached vertices in \(X\). Its neighborhood is exactly the reached set \(T\), and \(|N(S)|<|S|\).
Each vertex is added to the queue at most once. The proof of the theorem justifies the output: it establishes both that all neighbors of \(S\) are reached and that the number of reached right-side vertices is smaller than the number of reached left-side vertices. If the matching already saturates \(X\), there are no starting vertices and no deficiency certificate is produced; in that case the procedure is simply unnecessary.
Worked Searches
Worked Example: One Unmatched Left Vertex
Let \(X=\{a,b,c,d\}\), \(Y=\{1,2,3,4\}\), and \(E=\{a1,b1,c2,c3,d3,d4\}\). Take \(M=\{a1,c2,d3\}\). The vertices \(b\) and \(4\) are unmatched. This matching is maximum: among \(a,b\), which have only the neighbor \(1\), at most one can be matched; among \(c,d\), at most two can be matched. Thus every matching has at most three edges, and \(M\) has three.
Start the queue with \(b\). The search follows the unmatched edge \(b1\), then the matched edge \(1a\). Vertex \(a\) has no other incident edge to follow. The queue empties, giving \(S=\{a,b\}\) and \(T=\{1\}\).
| Processed vertex | Allowed step | Newly reached vertex | Queue afterward |
|---|---|---|---|
| Start | Initialize with unmatched \(X\)-vertices | \(b\) | \([b]\) |
| \(b\in X\) | Unmatched edge \(b1\) | \(1\) | \([1]\) |
| \(1\in Y\) | Matching edge \(1a\) | \(a\) | \([a]\) |
| \(a\in X\) | No other unmatched incident edge | None | \([]\) |
Indeed, \(N(S)=N(\{a,b\})=\{1\}\), because both \(a\) and \(b\) are adjacent only to \(1\). Therefore \(|N(S)|=1<2=|S|\). The matching size check above also confirms that the input matching is maximum, as required for the certificate theorem.
Worked Example: Several Unmatched Left Vertices
Let \(X=\{a,b,c,d,e\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,b1,c2,d2,e3\}\). Take \(M=\{a1,c2,e3\}\). The unmatched left vertices are \(b\) and \(d\). The matching is maximum: at most one of \(a,b\) can be matched, at most one of \(c,d\) can be matched, and \(e\) can contribute at most one edge. Hence any matching has at most \(1+1+1=3\) edges, and \(M\) has three.
Initialize the queue with both unmatched vertices. From \(b\), the search reaches \(1\), then follows its matching edge to \(a\). From \(d\), it reaches \(2\), then follows its matching edge to \(c\). Neither \(a\) nor \(c\) has another incident edge. The full queue trace is:
| Processed vertex | Allowed step | Newly reached vertex | Queue afterward |
|---|---|---|---|
| Start | Initialize with unmatched \(X\)-vertices | \(b,d\) | \([b,d]\) |
| \(b\in X\) | Unmatched edge \(b1\) | \(1\) | \([d,1]\) |
| \(d\in X\) | Unmatched edge \(d2\) | \(2\) | \([1,2]\) |
| \(1\in Y\) | Matching edge \(1a\) | \(a\) | \([2,a]\) |
| \(2\in Y\) | Matching edge \(2c\) | \(c\) | \([a,c]\) |
| \(a,c\in X\) | No other unmatched incident edges | None | \([]\) |
The output is \(S=\{a,b,c,d\}\), \(T=\{1,2\}\). Directly, \(a,b\) have only neighbor \(1\), and \(c,d\) have only neighbor \(2\), so \(N(S)=\{1,2\}=T\). Thus \(|N(S)|=2<4=|S|\). The two unmatched starting vertices account for the difference: here \(|S|-|T|=2\).
Worked Example: An Isolated Left Vertex
Let \(X=\{a,b,c\}\), \(Y=\{1,2\}\), and \(E=\{a1,b2\}\). Use \(M=\{a1,b2\}\). This matching is maximum because \(Y\) has only two vertices, so no matching can contain more than two edges; \(M\) has two. Vertex \(c\) is isolated and is the only unmatched vertex in \(X\).
Initialize the queue with \(c\). It has no incident edges, so there are no search steps beyond processing \(c\). The queue trace is:
| Processed vertex | Allowed step | Newly reached vertex | Queue afterward |
|---|---|---|---|
| Start | Initialize with unmatched \(X\)-vertices | \(c\) | \([c]\) |
| \(c\in X\) | No incident edges | None | \([]\) |
The output is \(S=\{c\}\) and \(T=\varnothing\). Since \(c\) has no neighbors, \(N(S)=\varnothing\), so \(|N(S)|=0<1=|S|\). This also shows why the search must include unmatched left vertices even when they have no neighbors.
What the Certificate Tells You
The set \(S\) is a concrete witness that no matching can saturate \(X\): a matching that covered every vertex of \(S\) would have to use \(|S|\) distinct vertices of \(N(S)\), while \(|N(S)|<|S|\). The alternating search does more than announce that a matching is incomplete; it identifies where the shortage occurs. Its reached right-side set is exactly the neighborhood of the reached left-side set, not merely a subset of that neighborhood.
The maximum-matching assumption matters. The proof that every reached vertex of \(Y\) is matched used the fact that reaching an unmatched right vertex would create an alternating path that increases the matching size. Starting from a matching that is not maximum can therefore fail to produce a deficient set: the search may reach an unmatched vertex on the right instead, indicating that the current matching can be enlarged.
Common mistake: reversing the search direction. Suppose in the first example one incorrectly follows the matched edge out of \(b\). There is no such edge, so this mistaken search returns only \(S=\{b\}\) and might report \(N(S)=\varnothing\). That calculation is wrong: \(b\) is adjacent to \(1\), so \(N(\{b\})=\{1\}\) and \(1<1\) is false. The correct rule follows unmatched edges from left to right and matched edges from right to left. It reaches \(a\) as well as \(b\), giving \(S=\{a,b\}\), \(N(S)=\{1\}\), and \(1<2\).
When implementing the procedure, mark vertices when they are added to the queue, not only when they are processed. This prevents repeated additions if several edges lead to the same vertex. Also start from all unmatched vertices of \(X\): in the second example, starting only from \(b\) would miss the separate reachable pair \(d,c\), and the resulting set would not capture the full deficiency of the search.
Check Your Understanding
For each question, distinguish the matching edges from the edges followed during the alternating search.
- In the second worked example, list the unmatched starting vertices and give the final sets \(S\) and \(T\).
- Why does reaching an unmatched vertex of \(Y\) contradict the assumption that \(M\) is maximum?
- Explain why every neighbor of a reached vertex in \(X\) is reached in \(Y\), whether or not their joining edge belongs to \(M\).
- If the search returns \(S\) and \(T\), what equality relates \(T\) to \(N(S)\), and what strict inequality certifies deficiency?
- For the graph \(X=\{p,q\}\), \(Y=\{u\}\), \(E=\{pu,qu\}\), and \(M=\{pu\}\), run the search and state the resulting deficient set.