On the hard direction proof of Hall's theorem for bipartite graphs

283 Views Asked by At

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?

1

There are 1 best solutions below

2
On 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.