I'm struggling on this question and any hints (not full answers) would be greatly appreciated.
Consider Bipartite Graph G with vertex Classes A and B of the same size. I need to use Hall's Theorem to show that is |N(S)| > |S| for all subsets S of A then for any edge e, G contains a perfect matching containing e.
Thanks!
Note that Hall's condition usually doesn't have a strict inequality. So try removing the specified edge and its endpoints from the graph. How much smaller could the neighborhood of any set $S\subseteq A$ have become?