Let $G=(A, B, E)$ is bipartite graph. In order to find a match in the $G$ graph so that there are no unpaired elements in the set $A$, the necessary and sufficient condition is that it is $|A-N(T)|\leq |B-T|$ for every $T \subset B$.
I know Hall Theorem. I tried a lot but I couldn't prove this proposition. Can you show me this prove? Thank you for visiting my question.
Here are a few hints to get you started:
$G$ has a complete matching from $A$ to $B$ $\implies |A - N(T)| \leq |B - T|$ for every subset $T \subseteq B$.
Let $T \subseteq B$ be arbitary. Let $S = A \setminus N(T)$ and use Hall's theorem on $S$. This would give $|S| \leq |N(S)|$. Try and reason why $T \cap N(S) = \varnothing$. From this conclude that $|N(S)| \leq |B - T|$ and so $|A - N(T)| = |S| \leq |N(S)| \leq |B - T|$, as desired.
$|A - N(T)| \leq |B - T|$ for every subset $T \subseteq B$ $\implies$ $G$ has a complete matching.
Let $S \subseteq A$ be arbitary. Consider $T = B \setminus N(S)$. Then $|A - N(T)| \leq |B - T|$ by assumption. Argue that $S \cap N(T) = \varnothing$ and conclude that $|S| \leq |A - N(T)| \leq |B - T| = |N(S)|$. Since $S$ was arbitary, Hall's theorem implies that $G$ has a complete matching.