Question: Suppose that $G$ is bipartite with vertex classes $A$ and $B$ so that $|A|=|B|=n$. Suppose that $δ(G) ≥ n/2$. Use Hall’s theorem to show that G has a perfect matching.
My Answer: Let $G$ be a bipartite graph with vertex classes $A$ and $B$ such that $|A|=|B|=n$. Consider any set $S$ in $A$. Let $t$ be the number of edges from $S$ to $N_G(S)$. Since the minimum degree of every vertex is at least $\frac{n}{2}$ we have that $t \geq \frac{n}{2}|S|$. We also have that $\frac{n}{2}|N_G(S)| \geq t$ as the set $N_G(S)$ may have other neighbors in $A$ which are outside of $S$. Combining these inequalities gives $\frac{n}{2}|N_G(S)| \geq \frac{n}{2}|S|$, hence $|N_G(S)| \geq |S|$. So by Hall's Theorem there is a matching covering all of $A$, or equivalently every maximum matching covers $A$. Using a similar argument we have that every maximum matching covers $B$. Thus, $G$ contains a perfect matching.
I just wanted to check that what I have done here is correct as I was initially confused with the $δ(G) ≥ n/2$ part.
Best Answer
Your argument is incorrect. You have not justified your claim that $\frac n2|N_G(S)|\ge t.$ You have not really used the assumption that $\delta(G)\ge n/2$; why doesn't the same argument work with $n/2$ replaced by any other nonzero quantity? What happens if you try the same argument assuming $\delta(G)\ge1$ instead of $\delta(G)\ge n/2$?