Bipartite Graphs and Perfect Matchings when |A|=|B|=n Question: Consider a bipartite graph G with vertex classes A and B, where $|A|=|B|=n$. Show that if $|N(S)|>|S|$ for all $S \subset A$, then for any edge e of G, G contains a perfect matching which contains e.
Answer: So far I have shown that G contains a matching which contains e using Hall's Theorem however I am unsure about how to show that this matching is perfect. I have the following theorem: 
Let G be a bipartite graph with vertex classes A and B and $|A|=|B|=n$. If $\delta (G) \geq n/2$, then G has a perfect matching.
But I don't know how to show the $\delta (G) \geq n/2$ part in this case? 
 A: I think Hall's theorem is sufficient. Note that in your problem you have $|N(S)| > |S|$ with strict inequality (presumably for nonempty strict subsets $S$ of $A$), while Hall's theorem only requires the non-strict inequality.
Let $G'$ be the result of removing the edge $e$ and its two vertices (call them $a \in A$ and $b \in B$) from $G$.
Let $A'$ and $B'$ be the partition of the vertices of $G'$.
It then suffices to show that the smaller bipartite graph $G'$ satisfies its own condition for Hall's theorem.
Let $S'$ be any subset of $A'$. Since it is a subset of $A$ as well, it satisfies $|S'| < |N_G(S')|$, so
$$|S'| \le |N_G(S')| - 1 \le |N_{G'}(S')|$$
since the sets $N_{G'}(S')$ and $N_G(S')$ can differ by at most one vertex, namely $b$.
A: @Koala...
Can you mention cite the theorem which you have mentioned in the question
aka.
Let $G$ be a bipartite graph with vertex classes $A$ and $B$ and $|A|=|B|=n$. If $\delta(G)\geq n/2$, then $G$ has a perfect matching.
Where did u find this theorem? 
I know a similar theorem called Dirac's theorem, but that works for general graphs which have minimum degree of each vertex to be at least $n/2$. 
