Proof explanation of Hall's Marriage Theorem?

1.8k Views Asked by At

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?

enter image description here enter image description here enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

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$.