Why Hall’s Condition Is Necessary

The Counting Question

Suppose each person in one group must be assigned a distinct acceptable object from another group. If a group of \(k\) people collectively has fewer than \(k\) acceptable objects, no assignment can give all \(k\) people different objects. This simple counting obstruction is the necessary direction of Hall’s condition. It says that a matching covering the whole left side cannot exist unless every subset of the left side has enough neighbors.

We work with finite simple bipartite graphs \(G=(X\cup Y,E)\), where \(X\) and \(Y\) are disjoint vertex sets and every edge has one endpoint in each set. 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; vertices of \(Y\) need not all be matched. For \(S\subseteq X\), its neighborhood is the set of vertices of \(Y\) adjacent to at least one vertex of \(S\):

N(S)=\{y\in Y:\ xy\in E\text{ for some }x\in S\}.

The relevant inequality compares the number of vertices in \(S\) with the number of distinct vertices in \(N(S)\). It is not a comparison with the number of edges leaving \(S\).

The Necessary Condition

Proposition: Let \(G=(X\cup Y,E)\) be a finite bipartite graph. If \(G\) has a matching that saturates \(X\), then every subset \(S\subseteq X\) satisfies \(|N(S)|\ge |S|\).

Proof. Let \(M\) be a matching that saturates \(X\), and fix any subset \(S\subseteq X\). For each \(x\in S\), saturation gives a matching edge incident with \(x\). Let \(f(x)\in Y\) be the other endpoint of this edge. Since \(xf(x)\in E\) and \(x\in S\), the definition of neighborhood gives \(f(x)\in N(S)\). Thus \(f\) maps \(S\) into \(N(S)\).

The map is one-to-one: if \(f(x)=f(x')\) for two vertices \(x,x'\in S\), then the two matching edges incident with \(x\) and \(x'\) share their endpoint in \(Y\). A matching has no shared endpoints, so this can happen only when \(x=x'\). Therefore \(S\) maps injectively into \(N(S)\), and both sets are finite, so \(|S|\le |N(S)|\). If \(S=\varnothing\), both cardinalities are zero and the same inequality holds. Since \(S\) was arbitrary, the inequality holds for every subset of \(X\). \(\square\)

The argument is a counting proof: every left-side vertex in \(S\) uses one matched partner, and no two vertices of \(S\) can use the same partner. Those partners all belong to \(N(S)\), so \(N(S)\) must contain at least \(|S|\) vertices. The proof does not require a matching that covers \(Y\), nor does it require \(|X|=|Y|\).

Set Families and Distinct Representatives

Definition: For a finite family of sets \(A_x\), indexed by \(x\in X\), a system of distinct representatives is a choice of an element \(r_x\in A_x\) for each \(x\in X\), with \(r_x\ne r_{x'}\) whenever \(x\ne x'\).

To express this with a graph, take \(X\) as the index set of the family, take \(Y=\bigcup_{x\in X}A_x\), and join \(x\in X\) to \(y\in Y\) exactly when \(y\in A_x\). This is the incidence graph of the family. A system of distinct representatives is exactly a matching that saturates \(X\): the edge joining \(x\) to its chosen representative records the choice, and distinct representatives ensure that the chosen edges share no endpoint. For \(S\subseteq X\), the graph neighborhood is \(N(S)=\bigcup_{x\in S}A_x\). Consequently the proposition gives the following necessary condition:

Set-family consequence: If a finite family \((A_x)_{x\in X}\) has distinct representatives, then for every \(S\subseteq X\), \(\left|\bigcup_{x\in S}A_x\right|\ge |S|\).

This conclusion is only a necessary condition here: the counting argument proves that a matching covering \(X\) forces all these inequalities. It does not, by itself, prove that the inequalities guarantee such a matching.

Worked Example: Checking Every Subfamily

Consider \(X=\{a,b,c\}\) and the family \(A_a=\{1,2\}\), \(A_b=\{2,3\}\), and \(A_c=\{1,4\}\). Its incidence graph has vertex sets \(X=\{a,b,c\}\) and \(Y=\{1,2,3,4\}\), and edge set \(E=\{a1,a2,b2,b3,c1,c4\}\). The edges \(a2,b3,c4\) form a matching: each is in \(E\), and their endpoints are all distinct. The matching saturates \(X\).

Check the neighborhood inequality for every subset. For the empty subset, the union is empty, so both sizes are \(0\). For the three one-element subsets, the unions are \(A_a=\{1,2\}\), \(A_b=\{2,3\}\), and \(A_c=\{1,4\}\); each has size \(2\), while each index set has size \(1\). For the two-element subsets, the unions are \(A_a\cup A_b=\{1,2,3\}\), \(A_a\cup A_c=\{1,2,4\}\), and \(A_b\cup A_c=\{1,2,3,4\}\); their sizes are \(3,3,4\), respectively, each at least \(2\). For the full subset, \(A_a\cup A_b\cup A_c=\{1,2,3,4\}\), of size \(4\), which is at least \(3\).

Check: the displayed representatives are \(2\) for \(a\), \(3\) for \(b\), and \(4\) for \(c\). These are three distinct elements, so the matching really does saturate all three vertices of \(X\), as required by the proposition.

Worked Example: A Violating Subset Despite Enough Total Neighbors

Let \(X=\{a,b,c,d\}\), \(Y=\{1,2,3,4\}\), and \(E=\{a1,a2,b1,c2,d3,d4\}\). For the whole left side, \(N(X)=\{1,2,3,4\}\), so \(|N(X)|=4=|X|\). That total count alone does not rule out a matching saturating \(X\).

Now take the particular subset \(S=\{a,b,c\}\). Its neighbors are \(N(S)=\{1,2\}\): the edges from \(a\) end at \(1,2\), the edge from \(b\) ends at \(1\), and the edge from \(c\) ends at \(2\). Hence \(|S|=3\) and \(|N(S)|=2\), giving \(2<3\). The proposition shows that no matching can saturate \(X\), because any such matching would also have to match all three vertices of \(S\) to distinct vertices of \(N(S)\), which has only two vertices.

Check: the two vertices \(1,2\) are the entire neighborhood available to \(a,b,c\); vertices \(3,4\) are adjacent only to \(d\). Thus the four total neighbors cannot provide three distinct partners for \(S\). The obstruction is local to \(S\), even though the whole graph has four vertices on each side.

Worked Example: Following the Matched Partners

Let \(X=\{p,q,r,s\}\), \(Y=\{1,2,3,4\}\), and \(E=\{p1,p2,q1,q3,r2,r4,s4\}\). Consider \(M=\{p1,q3,r2,s4\}\). Every listed pair is an edge, and the endpoints in \(X\) are \(p,q,r,s\) while the endpoints in \(Y\) are \(1,3,2,4\). There are no repeated endpoints, so \(M\) is a matching and it saturates \(X\).

Choose \(S=\{p,q,r\}\). Its neighborhood is \(N(S)=\{1,2,3,4\}\): \(p\) is adjacent to \(1,2\), \(q\) to \(1,3\), and \(r\) to \(2,4\). Thus \(|S|=3\) and \(|N(S)|=4\), so the required inequality is \(4\ge3\). Under this matching, the partners of \(p,q,r\) are respectively \(1,3,2\). There are exactly three such partners, and they are distinct members of the four-element neighborhood.

Check: the partner map on \(S\) takes the values \(f(p)=1\), \(f(q)=3\), and \(f(r)=2\). These values are pairwise different, so it is an injection into \(N(S)\), matching the proof. The unused neighbor \(4\) does not cause a problem; the necessary condition is a lower bound, not an equality requirement.

What the Counting Argument Does—and Does Not—Count

The proof counts matched partners, one for each vertex in \(S\). It does not count all edges from \(S\). Several edges can lead to the same neighbor, and that neighbor can serve as the matched partner of at most one vertex. For this reason, the number of edges incident with \(S\) is not a substitute for \(|N(S)|\).

A practical consequence is that one violating subset is enough to prove that no matching saturates \(X\). To establish this obstruction, it is sufficient to identify \(S\), list its distinct neighbors, and compare the two cardinalities. On the other hand, checking only \(S=X\) cannot rule out a matching when the whole left side has enough neighbors: the second example has \(|N(X)|=|X|\), but its smaller subset violates the inequality.

Common Pitfall: Counting Edges Instead of Neighbors

In the second example, for \(S=\{a,b,c\}\), there are four edges with an endpoint in \(S\): \(a1,a2,b1,c2\). A mistaken calculation might call this “four neighbors” and conclude that the subset has enough choices for three vertices. But those four edges end at only two distinct vertices, \(1\) and \(2\). The correct calculation is \(|N(S)|=|\{1,2\}|=2<3=|S|\). It is the number of distinct neighbors—not the number of incident edges—that must be compared with \(|S|\).

The key implication is therefore one-way: a matching saturating the left side forces the neighborhood inequality for every subset. The reason is the injection from each subset into its distinct matched partners. Any failure of the inequality certifies that such a matching is impossible.

Check Your Understanding

Use distinct neighbors, not edge counts, in each comparison.

In a bipartite graph with a matching saturating \(X\), why can two vertices of \(S\subseteq X\) not have the same matched partner?
For \(X=\{u,v\}\), \(Y=\{1,2\}\), and \(E=\{u1,u2,v1\}\), compute \(N(\{u,v\})\). Does the necessary inequality hold for this subset?
Explain why \(|N(X)|\ge |X|\) alone does not test the necessary condition for every subset.
Translate a system of distinct representatives for a set family into a matching in its incidence graph.
If some subset \(S\subseteq X\) has \(|N(S)|<|S|\), what does the proposition imply about matchings that saturate \(X\)?