I found in a book the following corollary of Hall's theorem:
Let $G=(A,B,E)$ be a bipartite graph. Suppose that $|A|=|B|=n$. If the minimal degree of $G$ is at least $n/2$ then $G$ has a matching.
I know how to prove that if the minimal degree of vertices in A is less than the maximal degree of vertices in B then $G$ has a matching, but apparently the strategy I used for this proof isn't working for the above corollary.
Any ideas?
By Hall's condition, it suffices to show that $|\Gamma(S)|\geq |S|$ for all $S\subseteq A$ and $S\subseteq B$. Let $S\subseteq A$. If $S=\emptyset$, then $|\Gamma(S)|\geq 0=|S|$. Assume further that $S\neq\emptyset$. If $|S|\leq \frac n 2$, then $|\Gamma(S)|\geq|\Gamma(v)|\geq\frac n 2$ where $v\in S$. If $|S|>\frac n 2$, then $|\Gamma(S)|=|B|\geq |S|$. Hence, the result follows.