Checking Neighborhoods One Subset at a Time
Hall’s condition turns a question about choosing distinct neighbors into a finite list of set-size checks. On a small graph, the most reliable method is literal: list every subset of the left side, compute its neighborhood as a union, and compare the two sizes. A matching found in the graph can then be checked directly; when the condition fails, the particular subset that fails shows where the obstruction lies.
Throughout, graphs are finite and simple. A graph is bipartite if its vertex set is divided into disjoint parts \(X\) and \(Y\), with every edge joining a vertex of \(X\) to a vertex of \(Y\). 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. This does not mean the matching is perfect: vertices in \(Y\) may be left unmatched, and if \(|X|\ne |Y|\), a matching saturating both parts is impossible.
The neighborhood is a union: \(N(S)=\bigcup_{x\in S}N(x)\), where \(N(x)=N(\{x\})\). Thus a right-side vertex adjacent to several vertices in \(S\) is counted once, not once for each edge. The empty set has empty neighborhood, so its check is \(0\ge0\). Hall’s condition is specifically a test for saturating the chosen side \(X\); it does not require \(|X|=|Y|\).
A Reliable Enumeration Method
For a left side with \(k\) vertices there are \(2^k\) subsets to inspect. In a small example, a table prevents omissions and makes the union calculations auditable. This update rule explains how to compute the entries.
Proof. A vertex \(y\in Y\) belongs to \(N(S\cup\{x\})\) exactly when it is adjacent to at least one vertex in \(S\cup\{x\}\). That happens exactly when \(y\in N(S)\) or \(y\in N(x)\), which is the definition of membership in \(N(S)\cup N(x)\). The two sets therefore contain exactly the same vertices. \(\square\)
When filling a table, start with the singleton neighborhoods and combine them by unions using this rule. It is useful to record the actual neighborhood set as well as its size: two different subsets may have neighborhoods of the same size, and the sets show exactly which right-side choices are available.
State \(X\), \(Y\), and the complete edge set, so each singleton neighborhood can be read from the graph.
Include \(\varnothing\), every singleton, and the full set; for each, take the union of its singleton neighborhoods.
For every row, compute \(|N(S)|\) and \(|S|\). A row with \(|N(S)|<|S|\) is a failure of Hall’s condition.
If proposing a matching, verify that every chosen edge exists, no two chosen edges share an endpoint, and every vertex of \(X\) is covered.
Worked Examples
Worked Example: A Graph That Passes the Check
Let \(G=(V,E)\) be bipartite with \(X=\{a,b,c\}\), \(Y=\{1,2,3\}\), and \(V=X\cup Y\). Let \(E=\{a1,a2,b2,b3,c1,c3\}\). Compute every neighborhood and test Hall’s condition on \(X\).
First, the singleton neighborhoods are \(N(a)=\{1,2\}\), \(N(b)=\{2,3\}\), and \(N(c)=\{1,3\}\). The remaining neighborhoods are unions of these sets:
| \(S\subseteq X\) | \(N(S)\) | \(|N(S)|\) | \(|S|\) |
|---|---|---|---|
| \(\varnothing\) | \(\varnothing\) | 0 | 0 |
| \(\{a\}\) | \(\{1,2\}\) | 2 | 1 |
| \(\{b\}\) | \(\{2,3\}\) | 2 | 1 |
| \(\{c\}\) | \(\{1,3\}\) | 2 | 1 |
| \(\{a,b\}\) | \(\{1,2\}\cup\{2,3\}=\{1,2,3\}\) | 3 | 2 |
| \(\{a,c\}\) | \(\{1,2\}\cup\{1,3\}=\{1,2,3\}\) | 3 | 2 |
| \(\{b,c\}\) | \(\{2,3\}\cup\{1,3\}=\{1,2,3\}\) | 3 | 2 |
| \(\{a,b,c\}\) | \(\{1,2\}\cup\{2,3\}\cup\{1,3\}=\{1,2,3\}\) | 3 | 3 |
Every row has \(|N(S)|\ge |S|\), so Hall’s condition holds. We can exhibit a matching saturating \(X\): choose \(\{a1,b2,c3\}\). Each edge belongs to \(E\), and its three endpoints in \(Y\) are distinct, so this is a matching. It covers \(a,b,c\), as required.
Check: the matching uses three distinct vertices of \(Y\), namely \(\{1,2,3\}\), and has size \(3=|X|\). The last table row also gives \(|N(X)|=3=|X|\); no right-side vertex has been counted twice in that union.
Worked Example: Two Vertices Compete for One Neighbor
Let \(X=\{a,b,c\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,b1,c2,c3\}\). The singleton neighborhoods are \(N(a)=\{1\}\), \(N(b)=\{1\}\), and \(N(c)=\{2,3\}\). List all subsets:
| \(S\subseteq X\) | \(N(S)\) | \(|N(S)|\) | \(|S|\) |
|---|---|---|---|
| \(\varnothing\) | \(\varnothing\) | 0 | 0 |
| \(\{a\}\) | \(\{1\}\) | 1 | 1 |
| \(\{b\}\) | \(\{1\}\) | 1 | 1 |
| \(\{c\}\) | \(\{2,3\}\) | 2 | 1 |
| \(\{a,b\}\) | \(\{1\}\cup\{1\}=\{1\}\) | 1 | 2 |
| \(\{a,c\}\) | \(\{1\}\cup\{2,3\}=\{1,2,3\}\) | 3 | 2 |
| \(\{b,c\}\) | \(\{1\}\cup\{2,3\}=\{1,2,3\}\) | 3 | 2 |
| \(\{a,b,c\}\) | \(\{1\}\cup\{1\}\cup\{2,3\}=\{1,2,3\}\) | 3 | 3 |
The row \(S=\{a,b\}\) fails: \(|N(S)|=1<2=|S|\). The two vertices \(a\) and \(b\) can only be matched to vertex \(1\), so they cannot both be covered by a matching. For example, \(\{a1,c2\}\) is a matching of size \(2\), but leaves \(b\) unmatched; choosing \(b1\) instead leaves \(a\) unmatched. A matching saturating all three vertices of \(X\) would need three distinct neighbors, and this pair has only one available.
Check: the edge set contains exactly the four listed edges, and \(N(X)=\{1,2,3\}\) has size \(3\). Thus the full set passes, but the smaller subset \(\{a,b\}\) fails; checking only the full left side would miss the obstruction.
Worked Example: Only the Full Set Fails
Let \(X=\{a,b,c\}\), \(Y=\{1,2\}\), and \(E=\{a1,b2,c1,c2\}\). Thus \(N(a)=\{1\}\), \(N(b)=\{2\}\), and \(N(c)=\{1,2\}\). The complete subset check is:
| \(S\subseteq X\) | \(N(S)\) | \(|N(S)|\) | \(|S|\) |
|---|---|---|---|
| \(\varnothing\) | \(\varnothing\) | 0 | 0 |
| \(\{a\}\) | \(\{1\}\) | 1 | 1 |
| \(\{b\}\) | \(\{2\}\) | 1 | 1 |
| \(\{c\}\) | \(\{1,2\}\) | 2 | 1 |
| \(\{a,b\}\) | \(\{1\}\cup\{2\}=\{1,2\}\) | 2 | 2 |
| \(\{a,c\}\) | \(\{1\}\cup\{1,2\}=\{1,2\}\) | 2 | 2 |
| \(\{b,c\}\) | \(\{2\}\cup\{1,2\}=\{1,2\}\) | 2 | 2 |
| \(\{a,b,c\}\) | \(\{1\}\cup\{2\}\cup\{1,2\}=\{1,2\}\) | 2 | 3 |
Every proper subset passes, but \(X\) itself fails because \(|N(X)|=2<3=|X|\). There cannot be a matching saturating \(X\): three covered left-side vertices would require three distinct right-side endpoints, while \(Y\) has only two vertices. A matching of size \(2\), such as \(\{a1,b2\}\), is possible, but it leaves \(c\) unmatched.
Check: \(\{a,c\}\) has neighborhood \(\{1,2\}\), of size \(2\), and \(\{b,c\}\) has the same neighborhood, also of size \(2\). The failed inequality occurs only when all three left vertices are combined.
The Two-Vertex Case
For a left side of size two, the full subset check has a concise exact interpretation. This small case is useful for verifying tables and for seeing how the sizes of singleton neighborhoods and their union interact.
Proof. The subsets of \(X\) are \(\varnothing,\{a\},\{b\},\{a,b\}\). Thus Hall’s condition says exactly that \(N(a)\) and \(N(b)\) are nonempty and \(|N(a)\cup N(b)|\ge2\). If a matching saturates \(X\), its two edges use distinct right-side endpoints \(y_a\in N(a)\) and \(y_b\in N(b)\). Therefore both singleton neighborhoods are nonempty and the union contains the two distinct vertices \(y_a,y_b\).
Conversely, assume the stated neighborhood conditions. Choose \(y_a\in N(a)\). If there is a vertex \(y_b\in N(b)\) with \(y_b\ne y_a\), the edges \(ay_a\) and \(by_b\) form a matching saturating \(X\). If there is no such \(y_b\), then the nonempty set \(N(b)\) must equal \(\{y_a\}\). Since \(|N(a)\cup N(b)|\ge2\), there is a vertex \(y'\in N(a)\) with \(y'\ne y_a\). Now \(ay'\) and \(by_a\) form a matching saturating \(X\). Both directions hold. \(\square\)
For three or more left-side vertices, the same simple two-neighborhood argument does not settle the problem: subsets of several vertices must also be checked. The three examples show why it is important to identify the exact failing subset rather than infer the answer from singleton neighborhoods or from the full-set row alone.
Common Pitfall: Adding Neighborhood Sizes
A union does not count a shared neighbor twice. In the second example, \(N(a)=\{1\}\) and \(N(b)=\{1\}\). A mistaken calculation might add the singleton sizes and write \(|N(\{a,b\})|=|N(a)|+|N(b)|=1+1=2\), then conclude that the pair passes. The correct calculation is
The mistake treats the same right-side vertex as two distinct choices. In general, use a set union first and count its distinct elements second. Also, do not stop after checking singletons: the second example passes every singleton check and the full-set check, yet the pair \(\{a,b\}\) fails.
Check Your Understanding
For each question, calculate neighborhoods as sets before comparing their sizes.
- For \(X=\{p,q\}\), \(Y=\{1,2\}\), and \(E=\{p1,q1,q2\}\), list the four neighborhoods and decide whether Hall’s condition holds.
- In the first worked example, why does \(N(\{a,b\})\) have three elements rather than four?
- Give a matching saturating \(X=\{a,b,c\}\) in the first example and verify that no two chosen edges share an endpoint.
- In the third example, identify the only subset that fails Hall’s condition and give its two cardinalities.
- For a bipartite graph with \(X=\{u,v\}\), explain why nonempty \(N(u)\), nonempty \(N(v)\), and \(|N(u)\cup N(v)|\ge2\) suffice to find a matching saturating \(X\).