Hall Deficiency and Maximum Partial Representations

From Hall’s Condition to a Deficiency Formula

Hall’s condition asks whether every indexed set can receive a distinct representative: for each collection of indices, its sets must contain at least as many available elements as there are indices. When that condition fails, it is useful to know more than just that a full representation is impossible. The deficiency formula gives the exact number of indices that must remain unrepresented in the best possible partial representation.

Throughout, $G=(X\cup Y,E)$ is a finite simple bipartite graph with disjoint vertex sets $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 no two of which share an endpoint. Its size is its number of edges; a maximum matching is one of largest size. A matching need not cover every vertex.

Definition: The deficiency of $S\subseteq X$ is $\operatorname{def}(S)=|S|-|N(S)|$. The maximum deficiency of the $X$-side is $D_X(G)=\max_{S\subseteq X}\operatorname{def}(S)$. The maximum is taken over all subsets, including $S=\varnothing$, so $D_X(G)\ge 0$.

If $X$ indexes sets $A_x\subseteq Y$, put an edge $xy$ exactly when $y\in A_x$. Then $N(S)=\bigcup_{x\in S} A_x$, and $\operatorname{def}(S)$ measures how many more indices than available elements occur in that subcollection. A matching represents distinct representatives for the indices it covers. Thus a matching of size $q$ represents exactly $q$ indices and leaves $|X|-q$ unrepresented.

The Maximum Partial Representation Theorem

Theorem (Hall deficiency formula): For every finite bipartite graph $G=(X\cup Y,E)$, the size of a maximum matching is $$ \nu(G)=|X|-D_X(G)=|X|-\max_{S\subseteq X}\bigl(|S|-|N(S)|\bigr). $$ Consequently, the fewest vertices of $X$ left uncovered by a matching is $D_X(G)$.

Proof. Let $M$ be any matching, and fix $S\subseteq X$. At most $|N(S)|$ vertices of $S$ can be matched, because each matched vertex of $S$ must be paired with a different vertex of $N(S)$. Therefore at least $|S|-|N(S)|$ vertices of $S$ are unmatched whenever this difference is positive. Since the empty set has deficiency zero, this implies that the total number of unmatched vertices of $X$ is at least $D_X(G)$. In particular, if $M$ is maximum, then $|M|\le |X|-D_X(G)$.

For the reverse inequality, take a maximum matching $M$. Starting from every unmatched vertex of $X$, follow edges not in $M$ from $X$ to $Y$, and edges in $M$ from $Y$ to $X$. Let $S\subseteq X$ be the set of reachable vertices in $X$, and $T\subseteq Y$ the set of reachable vertices in $Y$. A reachable unmatched vertex of $Y$ would give an alternating path from an unmatched vertex of $X$ to an unmatched vertex of $Y$. Taking a shortest such route makes it a path; exchanging its matching and nonmatching edges would produce a matching with one more edge. This contradicts the maximal size of $M$. Thus every vertex of $T$ is matched.

We have $T=N(S)$. Indeed, if $x\in S$ and $xy\notin M$, the search can follow $xy$, so $y\in T$. If $x\in S$ and $xy\in M$, then $x$ is not an unmatched starting vertex; it was reached along its matching edge from $y$, so $y\in T$ as well. This proves $N(S)\subseteq T$. Conversely, every reachable $y\in T$ is reached from a vertex $x\in S$ along an edge $xy$, so $y\in N(S)$.

Every vertex of $T$ has a matching partner in $S$, because the search follows its matching edge to that partner. Every matched vertex of $S$ has its partner in $T$: it is not a starting vertex, and it was reached from that partner along a matching edge. These matching edges therefore pair the vertices of $T$ bijectively with the matched vertices of $S$. The other vertices of $S$ are exactly the unmatched starting vertices. If their number is $u$, then $|S|=|T|+u$, so $\operatorname{def}(S)=|S|-|N(S)|=|S|-|T|=u$. The number $u$ is the total number of unmatched vertices of $X$, since every unmatched vertex of $X$ was a starting vertex. Thus $D_X(G)\ge u$. The first part of the proof gave $u\ge D_X(G)$, hence $u=D_X(G)$. Since $|M|=|X|-u$, the formula follows. $\square$

The argument includes degenerate cases. If $X=\varnothing$, the only subset is empty and both sides of the formula are zero. If $X$ is nonempty but has no edges, taking $S=X$ gives deficiency $|X|$, and the maximum matching has size zero. Vertices of $Y$ with no incident edges do not affect any neighborhood.

Worked Examples

Worked Example: Two Indices Share One Available Element

Let $X=\{1,2,3,4\}$, $Y=\{a,b,c,d\}$, and $E=\{1a,2a,3b,4c,4d\}$. Regard each $i\in X$ as indexing the set $A_i=N(i)$. Thus $A_1=A_2=\{a\}$, $A_3=\{b\}$, and $A_4=\{c,d\}$. Find the largest partial representation and verify the maximum deficiency.

For any $S\subseteq X$, let $i=|S\cap\{1,2\}|$, and let $\epsilon_3,\epsilon_4$ be $1$ if $3,4\in S$, respectively, and $0$ otherwise. The size of $S$ is $i+\epsilon_3+\epsilon_4$. Its neighborhood contains $a$ exactly when $i>0$, contains $b$ exactly when $\epsilon_3=1$, and contains both $c,d$ exactly when $\epsilon_4=1$. Therefore $$ |N(S)|=\mathbf{1}_{i>0}+\epsilon_3+2\epsilon_4,\qquad \operatorname{def}(S)=i-\mathbf{1}_{i>0}-\epsilon_4, $$ where $\mathbf{1}_{i>0}$ is $1$ when $i>0$ and $0$ otherwise.

If $i=0$, the deficiency is $-\epsilon_4$, which is at most $0$. If $i=1$, it is $-\epsilon_4$, also at most $0$. If $i=2$, it is $1-\epsilon_4$, which is at most $1$ and equals $1$ when $\epsilon_4=0$. These cases include either value of $\epsilon_3$, whose contribution cancels. Hence $D_X(G)=1$.

The formula gives $\nu(G)=4-1=3$. A matching of size $3$ is $\{1a,3b,4c\}$. No matching can be larger: vertices $1$ and $2$ can only be matched to $a$, so at most one of them can be covered, while vertices $3$ and $4$ contribute at most one matched edge each. Thus every matching has size at most $1+1+1=3$, confirming the answer directly. Index $2$ is left without a representative in the displayed matching.

Worked Example: Two Indices Must Remain Unrepresented

Let $X=\{1,2,3,4\}$, $Y=\{a,b\}$, and $E=\{1a,1b,2a,2b,3a,3b\}$. The first three indices each have available set $\{a,b\}$, while index $4$ has the empty set. For $S\subseteq X$, put $i=|S\cap\{1,2,3\}|$ and let $\epsilon_4=1$ if $4\in S$, and $0$ otherwise. If $i=0$, then $|N(S)|=0$ and $\operatorname{def}(S)=\epsilon_4\le 1$. If $i>0$, then $|N(S)|=2$ and $\operatorname{def}(S)=i+\epsilon_4-2\le 3+1-2=2$. The upper value $2$ is attained for $S=X$, whose neighborhood is $\{a,b\}$. Therefore $D_X(G)=2$, and the formula gives $\nu(G)=4-2=2$.

The matching $\{1a,2b\}$ has size $2$. No matching can have more than $2$ edges because there are only two vertices in $Y$, and matching edges use distinct vertices of $Y$. Thus the matching is maximum, and exactly two indices must remain unrepresented. In this example, indices $3$ and $4$ are left unrepresented; the empty set at index $4$ is permitted and is handled by the same formula.

Worked Example: Hall’s Condition Gives a Full Representation

Let $X=\{p,q,r\}$, $Y=\{1,2,3\}$, and $E=\{p1,p2,q1,r2,r3\}$. The indexed sets are $A_p=\{1,2\}$, $A_q=\{1\}$, and $A_r=\{2,3\}$. We check all subset sizes to find the maximum deficiency.

The empty subset has deficiency $0-0=0$. For singleton subsets, the neighborhood sizes are $|N(\{p\})|=2$, $|N(\{q\})|=1$, and $|N(\{r\})|=2$, so their deficiencies are $-1,0,-1$. For the three pairs, $N(\{p,q\})=\{1,2\}$, $N(\{p,r\})=\{1,2,3\}$, and $N(\{q,r\})=\{1,2,3\}$; their deficiencies are $2-2=0$, $2-3=-1$, and $2-3=-1$. Finally $N(X)=\{1,2,3\}$, so $\operatorname{def}(X)=3-3=0$. Thus $D_X(G)=0$ and $\nu(G)=3-0=3$.

The edges $\{q1,p2,r3\}$ form a matching of size $3$, covering all of $X$. It is maximum because no matching can cover more than the three vertices of $X$. This independently checks the formula’s prediction of a full system of distinct representatives.

Interpreting and Using the Formula

For an indexed family $(A_x)_{x\in X}$, the formula can be written $$ \text{fewest indices left without distinct representatives} =\max_{S\subseteq X}\left(|S|-\left|\bigcup_{x\in S}A_x\right|\right). $$ A subset with positive deficiency certifies an unavoidable shortfall: its indices have fewer available elements than their number. The theorem says that the largest such shortfall is not merely a lower bound; some matching leaves exactly that many indices uncovered.

Hall’s condition is the statement that $|N(S)|\ge |S|$ for every $S\subseteq X$. In the notation here, this is equivalent to $\operatorname{def}(S)\le 0$ for every $S$. Because the empty set has deficiency zero, Hall’s condition holds exactly when $D_X(G)=0$. The deficiency formula then says that a matching covers all of $X$ exactly in that case. This recovers the representative-system interpretation of Hall’s theorem while also quantifying what happens when the condition fails.

A Common Calculation Error

When several vertices have the same neighbor, count that neighbor only once in $N(S)$. Conversely, if one selected vertex has two distinct neighbors, both belong to $N(S)$, even if no matching uses both of them.

For instance, in the first example, take $S=\{4\}$. Here $i=0$, $\epsilon_3=0$, and $\epsilon_4=1$. A tempting but incorrect calculation is to use $i-\mathbf{1}_{i>0}$, obtaining $0$. That expression omits the contribution from vertex $4$. In fact, $|S|=0+0+1=1$ and $N(S)=\{c,d\}$, so $|N(S)|=2$ and $\operatorname{def}(S)=1-2=-1$. The correct general calculation includes the term $-\epsilon_4$: $i-\mathbf{1}_{i>0}-\epsilon_4=0-0-1=-1$. Although the omitted term does not change the maximum in that example, it gives an incorrect deficiency for this subset. Always compute both $|S|$ and $|N(S)|$ from their definitions before simplifying.

Check Your Understanding

For each question, use the definition of deficiency and the maximum partial representation theorem.

In a bipartite graph with $X=\{u,v,w\}$, suppose $N(\{u,v\})=\{a\}$. What lower bound does this set give on the number of unmatched vertices of $X$?
Explain why including the empty set in the maximum defining $D_X(G)$ ensures that $D_X(G)$ is never negative.
For $X=\{1,2\}$, $Y=\{a,b\}$, and $E=\{1a,2a\}$, calculate the deficiency of every subset of $X$, then find the maximum matching size.
In a set system, what graph edge should be included between an index $x$ and an element $y$? Explain why a matching represents distinct representatives for the indices it covers.
Why does a subset $S\subseteq X$ with $|N(S)|<|S|$ prove that no matching can cover every vertex of $X$?