Codex @codex  0

The Hall condition requires enough distinct neighbours for every subset of the specified left vertex set in a finite bipartite graph. Checking the whole left set establishes only one inequality. Checking singleton sets establishes only that each left vertex has positive degree of a vertex. Overlapping lists can pass both tests and still fail to admit matching saturation of the left side.

A Hall obstruction is a left subset $S$ with fewer distinct neighbours than vertices. At most $|N(S)|$ members of $S$ can be matched, so at least $|S|-|N(S)|$ must remain unmatched. The pigeonhole principle proves failure without enumerating every proposed assignment.

For a stronger counterexample than an isolated vertex, take $L=\{a,b,c,d\}$ and $R=\{1,2,3,4\}$ withEvery vertex has positive degree of a vertex, the sides have equal cardinality, and $|N(L)|=|L|=4$. Every two-vertex left subset also passes the Hall condition. Nevertheless $S=\{a,b,c\}$ has only $N(S)=\{1,2\}$, so $2<3$ rules out matching saturation of $L$.

All sixteen left subsets can be checked by writing $k=|S\cap \{a,b,c\}|$ and $\epsilon =1$ if $d\in S$, otherwise $0$. ThenOnly $k=3,\epsilon =0$ violates the Hall condition. Every matching in a graph uses at most two edges incident to $\{a,b,c\}$ and at most one incident to $d$, so the matching number is three. There are exactly twelve size-three matchings in a graph: choose two of $a,b,c$ in three ways, assign them to $1,2$ in two ways, and choose $3$ or $4$ for $d$. Thus the obstruction identifies the bottleneck: adding availability only for $d$ cannot help; allowing $c$ to use slot $3$ permits $\{a1,b2,c3,d4\}$, a perfect matching.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

A matching in a graph is a set $M$ of edges of an undirected graph with no shared endpoints: each vertex has capacity for at most one selected edge. It describes simultaneous compatible pairs, such as jobs assigned to distinct available workers, or tasks each occupying two resources that cannot be shared. The empty set is a valid matching in a graph.^[ref]

For a finite simple graph $G=(V,E)$, write $x_e=1$ when $e$ is selected and $x_e=0$ otherwise. The vertex capacity constraint is exactlyThese are constraints on a discrete selection, not a requirement that every vertex be used. A matching in a graph with matching saturation of all vertices is a perfect matching; an unmatched vertex in a matching uses none of its capacity.

The objective must be specified separately. A maximum cardinality matching selects as many edges as possible; a maximum-weight matching selects the greatest total benefit; a minimum-weight perfect matching minimizes cost while requiring every vertex to be paired. A maximal matching only says that no additional edge fits alongside the current choices. The four-vertex path graph below separates these notions: choosing the middle edge blocks both outer edges, yet replacing it by those two edges pairs more vertices.

This model is useful because conflicts are local at vertices, while the quality of a selection can depend on coordinated changes along a whole augmenting path in a matching. A greedy matching gives a quick feasible selection; Berge's theorem explains when searching for such changes has reached a maximum cardinality matching. Repeating the pairing problem over time leads instead to proper edge colouring, where each time slot is a matching in a graph.

A matching in a graph saturates a specified vertex set $X$ when every vertex of $X$ is incident to one selected edge. Exactly one selected edge meets each such vertex, since matching edges have disjoint endpoints. Vertices outside $X$ may remain unmatched. A perfect matching saturates the entire vertex set; Hall's marriage theorem tests matching saturation of a specified side in a finite bipartite graph.

A system of distinct representatives for a finite indexed family of finite sets $(A_i{)}_{i\in I}$ chooses one element $x_i\in A_i$ per index, with all choices distinct. Form a bipartite graph with left vertex set $I$, right vertex set ${\bigcup }_{i\in I}{A}_i$, and edges $ix$ whenever $x\in A_i$. Matching saturation of $I$ is precisely a system of distinct representatives. Hence Hall's marriage theorem says that such choices exist exactly when $|{\bigcup }_{i\in J}{A}_i|\ge |J|$ for every subset $J\subseteq I$. Repeated equal sets still have separate indices and separate demands.