Applying Hall’s Condition Carefully
Hall’s condition is a test about every subset of one specified part of a bipartite graph. Most errors come from changing one of those details: testing only individual vertices, counting edges instead of distinct neighbors, testing subsets on the wrong side, or treating a matching that covers one part as though it covers the whole graph. The examples below isolate these mistakes and show how to interpret the condition correctly.
Throughout, graphs are finite and simple. A bipartite graph \(G=(X\cup Y,E)\) has disjoint parts \(X\) and \(Y\), and every edge has one endpoint in each part. A matching is a set of edges no two of which share an endpoint. A matching saturates \(X\) if every vertex of \(X\) is an endpoint of one of its edges; it need not cover every vertex of \(Y\).
Hall’s theorem, established in the earlier material on Hall’s Marriage Theorem, says that a bipartite graph has a matching saturating \(X\) if and only if \(|N(S)|\ge |S|\) for every subset \(S\subseteq X\). The side \(X\) matters: this condition answers whether \(X\) can be saturated. We will use the theorem to diagnose errors, while proving directly the basic necessity and the relation between saturation and perfect matchings.
Why the Quantifier “Every Subset” Matters
Proof. Suppose a matching \(M\) saturates \(X\), and let \(S\subseteq X\). Each \(x\in S\) is matched to a vertex \(y\in Y\), and the matching edge shows that \(y\in N(S)\). Distinct vertices of \(S\) are matched to distinct vertices, because no two edges of \(M\) share an endpoint. Thus the partners of the vertices of \(S\) form a set of \(|S|\) distinct elements of \(N(S)\), so \(|N(S)|\ge |S|\). If \(S=\varnothing\), then \(N(S)=\varnothing\) and the inequality is \(0\ge0\). Taking \(S=\{x\}\) gives \(|N(\{x\})|\ge1\), which is exactly the requirement that \(x\) have a neighbor. \(\square\)
Worked Example: Individual Neighbors Are Not Enough
Let \(G\) have parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), with edge set \(E=\{a1,b1,c2,c3\}\). Each vertex of \(X\) has at least one neighbor: \(N(\{a\})=\{1\}\), \(N(\{b\})=\{1\}\), and \(N(\{c\})=\{2,3\}\). Therefore, the test on individual vertices passes.
Now test the subset \(S=\{a,b\}\). Both vertices have the same sole neighbor, so \(N(S)=\{1\}\), and \(|N(S)|=1<2=|S|\). Hall’s condition fails. Indeed, a matching can use vertex \(1\) for at most one of \(a,b\), so no matching can saturate \(X\).
Check: The matching \(\{a1,c2\}\) has two edges, and no matching has three: any matching saturating \(a\) and \(b\) would need two distinct partners in \(N(\{a,b\})=\{1\}\), which has only one vertex. This confirms the obstruction found by Hall’s condition.
The singleton checks are necessary but are not a replacement for checking larger subsets. A set can fail Hall’s condition because its vertices collectively have too few options, even when each vertex has several options on its own.
Count the Neighborhood, Not the Edges
To find \(N(S)\), collect all vertices on the opposite side adjacent to at least one member of \(S\), and count each vertex only once. It is a union of neighbor sets, not an intersection, and it is not a count of the edges leaving \(S\). Repeated edges from different vertices of \(S\) to the same neighbor contribute only one element to \(N(S)\).
Worked Example: Repeated Neighbors and a Deficient Set
Let \(G\) have parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), with edge set \(E=\{a1,a2,b1,c2\}\). Take \(S=\{a,b,c\}\). Listing the neighbors gives \(N(\{a\})=\{1,2\}\), \(N(\{b\})=\{1\}\), and \(N(\{c\})=\{2\}\). Their union is \(N(S)=\{1,2\}\), so \(|N(S)|=2<3=|S|\).
There are four edges with an endpoint in \(S\), namely \(a1,a2,b1,c2\), but there are only two distinct neighbors. Counting the four edge incidences instead of the two vertices would give the wrong quantity and falsely suggest that there are enough choices for three vertices. The overlap is exactly the issue: vertices \(a\) and \(b\) both use neighbor \(1\), while \(a\) and \(c\) both use neighbor \(2\).
Check: The matching \(\{a1,c2\}\) has two edges. Every edge in the graph has its \(Y\)-endpoint in \(\{1,2\}\), so a matching has at most two edges. Thus the largest possible matching has size two and cannot saturate the three vertices of \(X\), in agreement with the deficient set.
A common alternate error is to use only the common neighbors of the vertices in \(S\). The neighborhood is the union: a vertex belongs to \(N(S)\) if it is adjacent to at least one member of \(S\), not necessarily all of them. The next example gives a set for which that distinction changes the count.
Worked Example: The Neighborhood Is a Union
Let \(G\) have parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), with edge set \(E=\{a1,a2,b2,c2,c3\}\). For \(S=\{a,b\}\), the individual neighborhoods are \(N(\{a\})=\{1,2\}\) and \(N(\{b\})=\{2\}\). Hence \(N(S)=\{1,2\}\), the union, and \(|N(S)|=2=|S|\). The intersection is \(\{2\}\), but it is not the neighborhood of \(S\).
For completeness, the Hall counts for every subset of \(X\) are as follows:
| Subset \(S\) | \(N(S)\) | Comparison |
|---|---|---|
| \(\varnothing\) | \(\varnothing\) | \(0=0\) |
| \(\{a\}\) | \(\{1,2\}\) | \(2\ge1\) |
| \(\{b\}\) | \(\{2\}\) | \(1\ge1\) |
| \(\{c\}\) | \(\{2,3\}\) | \(2\ge1\) |
| \(\{a,b\}\) | \(\{1,2\}\) | \(2\ge2\) |
| \(\{a,c\}\) | \(\{1,2,3\}\) | \(3\ge2\) |
| \(\{b,c\}\) | \(\{2,3\}\) | \(2\ge2\) |
| \(\{a,b,c\}\) | \(\{1,2,3\}\) | \(3\ge3\) |
All subsets pass, so Hall’s theorem guarantees a matching saturating \(X\). One such matching is \(\{a1,b2,c3\}\). Each edge is in \(E\), and the three edges have distinct endpoints, so this matching does saturate \(X\).
Check: The matching has three edges, equal to \(|X|=3\), and uses the three distinct vertices \(1,2,3\) of \(Y\). It is therefore also a perfect matching.
Test Subsets on the Side You Want to Saturate
Hall’s condition is not a test that must be applied indiscriminately to both parts. To determine whether there is a matching saturating \(X\), test subsets \(S\subseteq X\). Testing subsets of \(Y\) instead addresses whether a matching can saturate \(Y\). When the parts have different sizes, the answers can differ.
Worked Example: Passing on One Side, Failing on the Other
Let \(G\) have parts \(X=\{x_1,x_2\}\) and \(Y=\{y_1,y_2,y_3\}\), with edge set \(E=\{x_1y_1,x_2y_2\}\). To ask whether \(X\) can be saturated, check its subsets: the empty set has no neighbors and size zero; \(\{x_1\}\) has neighborhood \(\{y_1\}\); \(\{x_2\}\) has neighborhood \(\{y_2\}\); and \(X\) has neighborhood \(\{y_1,y_2\}\), of size two. Each subset satisfies \(|N(S)|\ge |S|\).
Hall’s theorem therefore gives a matching saturating \(X\), namely \(\{x_1y_1,x_2y_2\}\). If we instead test the whole set \(Y\), its neighborhood is \(N(Y)=\{x_1,x_2\}\), so \(|N(Y)|=2<3=|Y|\). This failure correctly says that no matching can saturate \(Y\); it does not contradict the matching saturating \(X\).
Check: The displayed matching covers \(x_1,x_2,y_1,y_2\), but not the isolated vertex \(y_3\). It has two edges and saturates \(X\), while it cannot saturate \(Y\), which has three vertices.
Saturating One Part Is Not Always Perfect
Proof. Suppose \(|X|=|Y|=n\) and a matching saturates \(X\). Each of the \(n\) vertices of \(X\) is incident with a matching edge, and the matching property ensures these edges have \(n\) distinct endpoints in \(Y\). Since \(Y\) has exactly \(n\) vertices, those endpoints comprise all of \(Y\); the matching covers both parts and is perfect. Conversely, by definition, a perfect matching covers every vertex, so it saturates \(X\). This reasoning also includes \(n=0\): the empty matching covers every vertex of the empty graph. Finally, every matching edge in a perfect matching pairs one vertex of \(X\) with one vertex of \(Y\). Covering all vertices therefore requires the same number of vertices in each part, so \(|X|=|Y|\). \(\square\)
When the parts are unequal, “saturating \(X\)” and “perfect” must not be used interchangeably. A matching can cover every vertex on the smaller side while leaving vertices on the larger side unmatched. Hall’s condition for \(X\) establishes saturation of \(X\), not coverage of \(Y\). In an unequal bipartition, a perfect matching is impossible by the proposition, regardless of whether the smaller part can be saturated.
A Reliable Checklist
Before drawing a conclusion from Hall’s condition, make the target explicit: which part must the matching saturate? Then check subsets of that part, using the neighborhood on the opposite side. Count distinct neighbors in the union of their neighbor sets, and compare that number with the size of the subset. A single failing subset proves that saturation is impossible; to use Hall’s theorem to establish saturation, the inequality must hold for every subset. Finally, call the matching perfect only when it covers both parts.
Common mistake: “Every vertex of \(X\) has a neighbor, so Hall’s condition holds.” This checks only subsets of size one. In the first example, both \(a\) and \(b\) have a neighbor, but \(N(\{a,b\})=\{1\}\) has fewer vertices than \(\{a,b\}\). The correction is to test larger subsets as well, especially sets whose vertices share many of their neighbors.
Check Your Understanding
For each question, specify which side is being tested and count distinct neighbors.
- Let \(X=\{a,b\}\), \(Y=\{1,2\}\), and \(E=\{a1,a2,b2\}\). Does checking the two singleton subsets of \(X\) establish Hall’s condition? Which other subsets must be considered?
- For \(X=\{p,q,r\}\), \(Y=\{1,2,3\}\), and \(E=\{p1,p2,q1,r2\}\), find a subset of \(X\) that violates Hall’s condition. Why is counting edges from that subset incorrect?
- Suppose \(|X|=2\), \(|Y|=4\), and Hall’s condition holds for every subset of \(X\). What does Hall’s theorem guarantee, and what does it not guarantee?
- Prove that if a matching saturates \(X\), then no subset \(S\subseteq X\) can have fewer than \(|S|\) distinct neighbors.
- In a bipartite graph with equal-sized parts, explain why any matching saturating one part must also cover the other part.