Proof explanation of Hall's Marriage Theorem?
By John Peck •
$\begingroup$
I don't understand the last paragraph of this proof.
Why the result of $j+t$ vertices of $W_1$ consisting of these $t$ vertices together with the $j$ vertices removed from $W_1$ has $\color{red}{\textrm{fewer than}}$ $j+t$ neighbors?
1 Answer
$\begingroup$The set $W_1'$ has $j$ vertices and $|N(W_1')|=j$. For contradiction, we have assumed that there is a set $U \subseteq W_1 \setminus W_1'$ with $t$ vertices and whose neighborhood has size less than $t$. Thus the neighborhood of $W_1' \cup U$ has size less than $j+t$.
$\endgroup$ 2
