The hard-direction proof of Hall's Theorem in bipartite graphs is given as follows (Source Wikipedia):
We assume that there is no $X$-saturating matching and prove that Hall's
condition is violated for at least one $W \subseteq X$. Let $M$ be a maximum
matching, and $u$ a vertex not saturated by $M$. Consider all alternating
paths (i.e., paths in $G$ alternately using edges outside and inside $M$)
starting from $u$. Let the set of all points in $Y$ connected to $u$ by
these alternating paths be $Z$, and the set of all points in $X$ connected
to $u$ by these alternating paths (including $u$ itself) be $W$. No maximal
alternating path can end in a vertex in $Y$, lest it would be an
augmenting path, so that we could augment $M$ to a strictly larger
matching by toggling the status (belongs to $M$ or not) of all the edges
of the path. Thus every vertex in $Z$ is matched by $M$ to a vertex in $W \backslash \lbrace{ u \rbrace}$.
Conversely, every vertex v in $W \backslash \lbrace{ u \rbrace}$ is matched by $M$ to a
vertex in $Z$ (namely, the vertex preceding $v$ on an alternating path
ending at $v$). Thus, $M$ provides a bijection of $W \backslash \lbrace{ u \rbrace}$ and $Z$, which implies $|W| = |Z| + 1$.
All good so far. Now comes the part that throws me off a little …
On the other hand, $N_G(W) \subseteq Z$, where $N_G(W)$ is the neighbourhood of $W$ in $G$.
Let $v$ in $Y$ be connected to a vertex $w$ in $W$. If the edge $(w,v)$ is in $M$, then $v$ is
in $Z$ by the previous part of the proof, otherwise we can take an
alternating path ending in w and extend it with v, getting an
augmenting path and showing that v is in Z.
Shouldn't we interpret these last few lines as saying $|N_G(W)| = |Z|$ rather than the inequality that follows?
Hence, $|N_G(W)| \le |Z| = |W| − 1 < |W|$.
Since we have already shown that every $Z$ is matched by $W \backslash \lbrace{ u \rbrace}$, one might think that $N_G(W) \subseteq Z$ should hold with equality. Is there an example where the equality doesn't hold?
Best Answer
You are right that in this case, we actually always have $N_G(W) = Z$. Maybe the person writing the proof just didn't think to mention that, when $\subseteq$ is all that's necessary for the proof to work.