Hall's Marriage Theorem question

Question

I read Hall's marriage theorem from Discrete Mathematics by Rosen. I understood most of the theorem but have some questions on some parts of the proof :

Question : In both cases when considering all the subsets of $W_1$ with $j$ elements why does the author only consider $j$ from $1 \le j \le k$ when $W_1$ clearly has $k+1$ elements . Why not consider from $1 \le j \le (k+1)$ ?

Answer 1

The short answer is "because that makes the proof work".

The long answer is that there's two considerations at work here:

1. In case (i), we reduce the graph $H$ to a smaller graph $H'$ with bipartition $(W_1 - \{v\}, W_2 - \{w\})$. To check Hall's condition in $H'$, sets of size $1 \le j \le k$ are all we need. That makes it fine, in this case, to only consider those.
2. In case (ii), we apply the induction hypothesis to a graph $H'$ with bipartition $(W_1', W_2')$, where $|W_1'| = j$. To do this, $j$ should not be bigger than $k$. If we had $j = k+1$ here, then $H'$ would be all of $H$ (or at least $W_1'$ would be all of $W_1$), and we wouldn't be reducing to a smaller graph at all.

So the reason we ask for $j \le k$ is that case (ii) doesn't work otherwise. The reason we can get away with this is that case (i) doesn't require us to check $j=k+1$.