Recall that Hall$$s theorem provides a necessary and sufficient condition for complete matching

in a bipartite graph G$=($V$1\backslash$cup V$2,$ E$).$ Answer the following questions about this theorem with

detailed reasoning.

A$.$ According to this theorem, if $|$A$|<=|$N$($A$)|$ for every A$$V$1,$ then there is a complete

matching. In the proof it only considered two cases; case $1$: every set of j vertices has at

least j$+1$ neighbors and case $2$: there exists a set of j vertices that have j neighbors. Why

doesn't the proof need to consider the case that every j vertices have less than j

neighbors?

B$.$ In case $1,$ what problem will you face if instead of removing $1$ element out of j elements,

you remove $2$ elements?

C$.$ In case $2,$ we match a set of j vertices with j neighbors and remove the matched vertices,

then we say we should be able to apply IH on the rest of the graph. Otherwise, we show a

contradiction. Why can$$t we apply the same technique to case $1?$