Case 2.There exists a proper subset X ofU such that N(X)=X.Let F be the bipartite subgraph of G with partite sets X and N(X).Since Hall's condition is satisfied in F,it follows by the induction hypothesis that X can be matched to a subset of N(X).Indeed,since N(X)=X],the set X can be matched to N(X).Let M'be such a matching. Next,consider the bipartite subgraph H of G with partite sets U-X and W-N(X).Let S be a subset of U-X and let S'=N(S)n(W-N(X)). We show that |Ss S'l.By assumption,N(XUS)XUS.Hence N(X)川+ISI=lN(XUS)I≥X|+S