= Solution
Use the equivalent bipartite formulation: the left set has $m$ <vertices> and a <matching> must cover it. Necessity is immediate, since distinct matched partners for any left subset must all lie in its neighborhood.
For sufficiency, induct on $m$. The cases zero and one are immediate from the neighborhood condition. If a nonempty proper left subset $A$ satisfies $|N(A)|=|A|$, <induction> matches $A$ into $N(A)$. For the remaining left <vertices> and remaining right <vertices>, any subset $B$ has at least $|B|$ available neighbors: applying Hall's inequality to $A\cup B$ and removing the $|A|$ possible neighbors in $N(A)$ proves this. <Induction> supplies the second <matching>, and the two combine.
If no nonempty proper subset has equality, all such subsets have at least one extra neighbor. Choose any left <vertex> and one of its neighbors and match them. After deleting the pair, each nonempty subset of the remaining left side originally was proper and had at least $|B|+1$ neighbors; losing the chosen right <vertex> <leaves of a graph>[leaves] at least $|B|$. <Induction> completes the <matching>. Thus
$$
\boxed{|N(A)|\ge|A|\text{ for every left subset }A}
$$
is sufficient as well as necessary. If the right set is infinite, any subset with infinitely many neighbors automatically meets the finite inequalities, and the same finite-left <induction> applies.
Back to article page
