Representatives When the Two Sides Have Different Sizes
A family of sets may have more available objects than sets, or fewer objects than sets. The relevant question is not whether every set has at least one available object: several sets may have the same sole option. Instead, ask whether every group of sets collectively has enough available objects to give each set a different representative. Hall’s condition expresses exactly this requirement.
We use finite simple bipartite graphs \(G=(V,E)\) with a specified bipartition \(V=X\cup Y\), where \(X\cap Y=\varnothing\) and every edge has one endpoint in each part. For \(S\subseteq X\), its neighborhood in \(Y\) is \(N(S)=\{y\in Y: xy\in E\text{ for some }x\in S\}\). In a family of sets indexed by \(X\), \(N(S)\) is the set of objects available to at least one member of \(S\).
For a family of sets \((A_x)_{x\in X}\), a system of distinct representatives chooses one element \(a_x\in A_x\) for each \(x\), with all chosen elements different. Represent the family by a bipartite graph: join \(x\in X\) to \(y\in Y\) exactly when \(y\in A_x\). Choosing representatives is then the same as choosing matching edges that saturate \(X\).
Hall’s Condition
The condition concerns every subset of \(X\), not every subset of \(Y\). Its standard theorem is:
There are two important qualifications. First, the matching sought is required to cover \(X\), not necessarily \(Y\). Second, Hall’s condition is tested on subsets of the side one wants to saturate. If the goal is to saturate \(Y\), the corresponding condition is \(|N(T)|\ge |T|\) for every \(T\subseteq Y\), with neighborhoods now taken in \(X\).
The empty subset causes no exception: \(N(\varnothing)=\varnothing\), so the condition reads \(0\ge0\). If \(X=\varnothing\), the empty matching saturates \(X\), regardless of the size of \(Y\). It is perfect only when \(Y=\varnothing\).
What Unequal Sizes Imply
If a matching saturates \(X\), each vertex of \(X\) is paired with a different vertex of \(Y\). Thus \(|X|\le |Y|\). Hall’s condition also records this requirement by taking \(S=X\): it gives \(|N(X)|\ge|X|\), and \(N(X)\subseteq Y\), so \(|Y|\ge|X|\). If \(|X|>|Y|\), this one subset already violates Hall’s condition.
When \(|X|<|Y|\), a matching saturating \(X\) leaves at least one vertex of \(Y\) unmatched, so it cannot be perfect. When \(|X|=|Y|\), a matching saturating \(X\) also covers \(Y\): it uses \(|X|=|Y|\) distinct vertices of \(Y\), hence all of them. Therefore, in the equal-size case, saturating \(X\) is the same as being perfect. These distinctions matter whenever the aim is to assign a different object to every member of a family, while some available objects may remain unused.
Worked Example: More Available Objects Than Sets
Let \(G=(V,E)\) be bipartite with \(X=\{a,b,c\}\), \(Y=\{1,2,3,4\}\), and \(E=\{a1,a2,b2,b3,c3,c4\}\). Check Hall’s condition for \(X\), then distinguish a matching saturating \(X\) from a perfect matching.
The empty subset has neighborhood \(\varnothing\), so its sizes are \(0\) and \(0\). For the singletons, \(N(\{a\})=\{1,2\}\), \(N(\{b\})=\{2,3\}\), and \(N(\{c\})=\{3,4\}\); each neighborhood has size \(2\), which is at least the subset size \(1\).
For the two-element subsets, \(N(\{a,b\})=\{1,2,3\}\), \(N(\{a,c\})=\{1,2,3,4\}\), and \(N(\{b,c\})=\{2,3,4\}\). Their neighborhood sizes are respectively \(3,4,3\), each at least \(2\). Finally, \(N(X)=\{1,2,3,4\}\), whose size \(4\) is at least \(|X|=3\). This checks every subset of \(X\), so Hall’s condition holds.
The edges \(\{a1,b2,c3\}\) form a matching: their endpoints are all distinct, and every vertex of \(X\) is covered. Vertex \(4\) is unused. Because \(|X|=3\) and \(|Y|=4\), this matching is not perfect. Check: it has three edges, one incident with each of \(a,b,c\), and the three right endpoints are \(1,2,3\), leaving \(4\) uncovered.
Worked Example: Individual Choices Do Not Guarantee Distinct Representatives
Let \(G=(V,E)\) have \(X=\{a,b,c\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,b1,c2,c3\}\). Every vertex of \(X\) has a neighbor. Does Hall’s condition hold?
For \(S=\{a,b\}\), the only neighbor is \(1\), so \(N(S)=\{1\}\). Thus \(|N(S)|=1<2=|S|\), and Hall’s condition fails. In contrast, the singleton neighborhoods have sizes \(1,1,2\), respectively; checking only singletons would miss the obstruction.
The edges \(\{a1,c2\}\) form a matching, but it leaves \(b\) unmatched. No matching can cover both \(a\) and \(b\), because both have only the neighbor \(1\), and matching edges cannot share an endpoint. Thus there is no matching saturating \(X\). Check: the shortage is exactly visible in the subset \(\{a,b\}\): two vertices have only one available neighbor between them.
Worked Example: A Surplus Right Vertex Does Not Prevent Saturation
Let \(G=(V,E)\) have \(X=\{p,q\}\), \(Y=\{r,s,t\}\), and \(E=\{pr,ps,qs\}\). Check Hall’s condition, including the effect of the isolated vertex \(t\), and find a matching saturating \(X\).
The subsets of \(X\) are \(\varnothing,\{p\},\{q\},\{p,q\}\). Their neighborhoods are, respectively, \(\varnothing,\{r,s\},\{s\},\{r,s\}\). The corresponding neighborhood sizes \(0,2,1,2\) are at least the subset sizes \(0,1,1,2\). Hence Hall’s condition holds. The vertex \(t\) is isolated, but it belongs to \(Y\), not \(X\); its presence does not reduce any neighborhood of a subset of \(X\).
The edges \(\{pr,qs\}\) form a matching that saturates \(X\). The vertex \(t\) remains uncovered, so the matching is not perfect. Check: \(p,q\) are covered once each, and the chosen right endpoints \(r,s\) are distinct; \(|X|=2<3=|Y|\), as expected for a matching that saturates only \(X\).
Common Pitfalls and Uses
Wrong calculation: “Every vertex of \(X\) has at least one neighbor, so there are distinct representatives.” The failed example shows the error: \(a\) and \(b\) each have a neighbor, but \(N(\{a,b\})=\{1\}\), which has fewer elements than the two vertices needing representatives. Correction: test neighborhoods of all subsets of the side to be saturated, not just individual vertices or the whole side.
Wrong conclusion: “A matching that saturates \(X\) is perfect.” This is true only when it also covers \(Y\); in particular, if \(|X|<|Y|\), it cannot be perfect. Correction: specify which side must be covered. In assignment problems, the goal is often to assign one distinct option to every person or task in \(X\); unused options in \(Y\) are allowed.
Hall’s condition is useful because it turns a global selection question into a family of precise local capacity tests: every group \(S\) must have at least \(|S|\) options available in total. Its asymmetric form is a feature, not a defect. It lets us ask for a representative for every member of one designated side without demanding that every available object be used.
Check Your Understanding
For each question, identify which side is intended to be saturated before applying Hall’s condition.
- A bipartite graph has \(|X|=4\) and \(|Y|=6\). Can a matching saturating \(X\) be perfect? Explain.
- In the graph with \(X=\{u,v\}\), \(Y=\{1,2,3\}\), and \(E=\{u1,v1\}\), which subset of \(X\) violates Hall’s condition?
- Why does the subset \(S=\varnothing\) satisfy Hall’s condition for every finite bipartite graph?
- If \(|X|>|Y|\), which subset immediately shows that Hall’s condition fails?
- Can a graph with an isolated vertex in \(Y\) still have a matching saturating \(X\)? Explain what Hall’s condition tests.