Tight Hall Sets and Forced Matching Structure

When Hall’s Inequality Is Exact

Hall’s condition says that every group of left-side vertices has at least as many available neighbors as vertices in the group. When the two numbers are equal, there is no spare neighbor in that group: any matching that covers the group must use every one of those neighbors. This exactness can force the form of a representative assignment, even when several individual edges are available.

Throughout, \(G=(X\cup Y,E)\) is a finite simple bipartite graph with disjoint parts \(X\) and \(Y\), and every edge has one endpoint in each part. For \(S\subseteq X\), its neighborhood is \(N(S)=\{y\in Y: xy\in E\text{ for some }x\in S\}\). A matching is a set of edges with no shared endpoints; it saturates \(X\) if every vertex of \(X\) is incident to one of its edges. Equivalently, it assigns each \(x\in X\) a distinct neighbor in \(Y\), a system of distinct representatives.

Hall’s condition for a bipartite graph with left part \(X\) is \(|N(U)|\ge |U|\) for every \(U\subseteq X\). Hall’s theorem states that a matching saturating \(X\) exists if and only if this condition holds. We use that earlier result to show how tight sets constrain all such matchings, not just whether one exists.

The Forced-Use Principle

Proof. Every vertex \(x\in S\) is matched by \(M\) to a neighbor, and every neighbor of a vertex in \(S\) belongs to \(N(S)\). The matching therefore sends the \(|S|\) vertices of \(S\) to distinct vertices in \(N(S)\). Its image has size \(|S|\), while tightness gives \(|N(S)|=|S|\); hence the image is all of \(N(S)\). Thus every vertex of \(N(S)\) is already matched to a vertex of \(S\). Since a matching cannot use a vertex twice, no vertex of \(X\setminus S\) can be matched to \(N(S)\). If \(S=\varnothing\), both \(S\) and \(N(S)\) are empty and the conclusions hold vacuously. \(\square\)

The theorem is a statement about every matching saturating \(X\). It does not say that each vertex in \(S\) has a uniquely determined partner. Rather, the group \(S\) must use the whole neighborhood \(N(S)\), with the individual assignments forming a bijection. It also does not say there are no edges from \(X\setminus S\) into \(N(S)\); such edges may exist, but a saturating matching cannot select them.

How Tight Sets Split the Assignment Problem

A tight set separates the chosen edges of any saturating matching into two blocks: the vertices in \(S\) use \(N(S)\), and the vertices outside \(S\) use \(Y\setminus N(S)\). This is true even if there are edges between the two blocks in the graph. The next result says that, when Hall’s condition holds, each block is itself a valid smaller assignment problem.

Proof. For the first graph, take any \(U\subseteq S\). Its neighbors in that graph are exactly \(N(U)\): since \(U\subseteq S\), every neighbor of \(U\) is in \(N(S)\). Hall’s condition in \(G\) gives \(|N(U)|\ge |U|\). Thus the first graph satisfies Hall’s condition.

For the second graph, take any \(T\subseteq X\setminus S\). Its neighborhood within \(Y\setminus N(S)\) is \(N(T)\setminus N(S)\). Apply Hall’s condition in \(G\) to \(S\cup T\). Since \(S\) and \(T\) are disjoint and \(S\) is tight,

As \(|N(S)|=|S|\), subtracting these equal quantities gives \(|N(T)\setminus N(S)|\ge |T|\). This holds for every \(T\subseteq X\setminus S\), so the second graph also satisfies Hall’s condition. Hall’s theorem now gives a matching saturating the left part in each graph. Their vertex sets are disjoint on both sides, so the union is a matching and saturates \(X\). This also covers \(S=\varnothing\) or \(S=X\): the corresponding empty left part requires no edges, and the same inequalities apply. \(\square\)

The decomposition is useful in both directions. Any full matching restricts to matchings within the two blocks by the forced-use theorem. Conversely, if matchings for the two blocks have been found, their union gives a full assignment. Thus one may solve the two smaller problems separately and combine their solutions.

Nested Tight Sets Can Force Individual Choices

A tight set forces a group to use a group of neighbors; several overlapping or nested constraints can narrow the individual choices further. In particular, a singleton tight set forces its sole vertex to use its sole neighbor. Larger tight sets may then force additional choices after that neighbor is taken.

A Common Mistake and a Practical Use

Common mistake: In the second example, one might argue, “Since \(c1\) is an edge and \(c\) has not yet been assigned, assign \(c\) to 1.” That calculation checks only whether the edge exists; it does not check whether its endpoint is already used. The tight set \(\{a,b\}\) has two vertices and exactly two neighbors, so a matching saturating \(X\) must match \(a,b\) to both 1 and 2. The corrected conclusion is that \(c1\) is available in the graph but unavailable to a matching saturating \(X\).

When analyzing a representative problem, a tight set can therefore be used as a structural certificate. First verify \(|N(S)|=|S|\); then reserve all of \(N(S)\) for \(S\). The remaining choices for \(X\setminus S\) lie in \(Y\setminus N(S)\), and their Hall inequalities follow from applying the original condition to \(S\cup T\), as in the decomposition proof. This separates a global assignment into smaller pieces without assuming that cross-edges are absent.

Keep the distinction between possible edge and usable edge in a saturating matching in view. Tightness does not necessarily determine which vertex of \(S\) receives which neighbor, but it determines the set of neighbors the group must consume. Further tight sets, especially nested ones, may then turn that group-level restriction into forced individual assignments.