Strict Hall Conditions and Robust Representatives

Spare Neighbors and Robust Representatives

Hall’s condition asks whether each group of left-side vertices has enough right-side neighbors to receive distinct representatives. The strict version asks for one more neighbor than the group needs. That extra neighbor is useful: even if one right-side vertex disappears, each group still has enough available neighbors. We will prove this implication and examine what happens when the inequality is not strict.

Throughout, graphs are finite and simple. A bipartite graph \(G=(X\cup Y,E)\) has disjoint vertex sets \(X\) and \(Y\), and every edge joins a vertex of \(X\) to a vertex of \(Y\). For \(S\subseteq X\), its neighborhood is \(N_G(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\) belongs to one of its edges.

Deleting a right-side vertex \(y\in Y\) means removing \(y\) and all edges incident with it; the resulting graph is denoted \(G-y\). We use Hall’s theorem in its standard form: a finite bipartite graph with parts \(X,Y\) has a matching saturating \(X\) if and only if \(|N(S)|\ge |S|\) for every \(S\subseteq X\). Hall’s theorem and its proof appear in the earlier material on systems of distinct representatives.

The Robustness Theorem

Proof. If \(X=\varnothing\), the empty matching proves the claim. Suppose \(X\ne\varnothing\), fix \(y\in Y\), and consider any \(S\subseteq X\). If \(S=\varnothing\), then its neighborhood has size \(0=|S|\). If \(S\ne\varnothing\), deleting \(y\) removes at most one member of \(N_G(S)\), so \[ |N_{G-y}(S)|=|N_G(S)\setminus\{y\}|\ge |N_G(S)|-1\ge (|S|+1)-1=|S|. \] Thus \(G-y\) satisfies Hall’s condition for every \(S\subseteq X\). Hall’s theorem gives a matching in \(G-y\) saturating \(X\). \(\square\)

The proof identifies the exact role of the extra neighbor. For each set \(S\), there may be one fewer neighbor after a deletion, but the strict inequality guarantees that at least \(|S|\) remain. The deleted vertex need not belong to \(N_G(S)\): in that case the neighborhood does not shrink, and the same lower bound still holds.

More Deletions When There Is More Slack

The same counting argument gives a broader conclusion. The number of spare neighbors sets how many right-side vertices may be removed while retaining Hall’s condition.

Proof. Fix \(D\subseteq Y\) with \(|D|\le r\). For \(S=\varnothing\), the Hall inequality in the graph after deletion is \(0\ge0\). For any nonempty \(S\subseteq X\), at most \(|D|\) members of its neighborhood are removed. Consequently, \[ |N_{G-D}(S)|=|N_G(S)\setminus D| \ge |N_G(S)|-|D| \ge |S|+r-|D| \ge |S|. \] The graph after deletion therefore satisfies Hall’s condition for every subset of \(X\). Hall’s theorem supplies a matching saturating \(X\). If \(X=\varnothing\), the empty matching also gives the conclusion. \(\square\)

Taking \(r=1\) recovers the robustness theorem. For \(r=0\), the proposition is simply Hall’s theorem’s sufficiency direction. The assertion is a guarantee based on a uniform lower bound: if some set has fewer than \(|S|+r\) neighbors, the proposition does not decide whether particular deletions are safe.

Strict Hall as an Exact Single-Deletion Test

When \(Y\ne\varnothing\), the strict condition is not only sufficient: it is equivalent to having a saturating matching after every single right-side deletion. This gives a useful characterization of what the extra neighbor means.

Proof. The forward direction is the robustness theorem. For the reverse direction, suppose that every \(G-y\), for \(y\in Y\), has a matching saturating \(X\). Fix a nonempty set \(S\subseteq X\). First, \(N_G(S)\ne\varnothing\): choose any \(y_0\in Y\), which is possible because \(Y\ne\varnothing\). A matching in \(G-y_0\) saturating \(X\) matches every vertex of \(S\) to a right-side vertex, so \(S\) has a neighbor in \(G\). Now choose \(y\in N_G(S)\). A matching saturating \(X\) in \(G-y\) matches the vertices of \(S\) to \(|S|\) distinct vertices of \(N_G(S)\setminus\{y\}\). Hence \(|N_G(S)\setminus\{y\}|\ge |S|\), and therefore \(|N_G(S)|\ge |S|+1\). Since this holds for every nonempty \(S\), the strict Hall condition follows. \(\square\)

The assumption \(Y\ne\varnothing\) makes the family of single-deletion tests nonempty. If \(X=\varnothing\), the strict condition is vacuous and every deletion leaves the empty matching; the equivalence remains valid when \(Y\ne\varnothing\).

Common Pitfall: Checking Only the Whole Left Side

The strict inequality must hold for every nonempty subset of \(X\), not just for \(X\) itself. For example, let \(X=\{a,b,c\}\), \(Y=\{1,2,3,4\}\), and \(E=\{a1,a2,b1,b2,c3,c4\}\). The whole set has four neighbors, so \(|N(X)|=4=|X|+1\). But for \(S=\{a,b\}\), \(N(S)=\{1,2\}\), and \(|N(S)|=2<|S|+1=3\). Deleting \(1\) leaves \(a\) and \(b\) with only the shared neighbor \(2\), so they cannot both be matched.

A related counting error is to assume deletion always removes exactly one neighbor from every set. The correct identity is \(N_{G-y}(S)=N_G(S)\setminus\{y\}\): the neighborhood loses one vertex if \(y\in N_G(S)\), and loses none otherwise. In either case its size is at least \(|N_G(S)|-1\), which is the inequality used in the proof.

Robust representatives are useful when one option may become unavailable but the remaining choices must still permit a distinct assignment. The key question is not merely whether the original graph has a saturating matching. It is whether every group \(S\) has enough neighbors to absorb the loss. Strict Hall gives exactly one unit of protection against a single deletion; a surplus of \(r\) gives protection against up to \(r\) deletions.