Prove that a bipartite graph $G = \left(V,E\right)$ has a perfect matching $\iff$ $\vert N(S)\vert\geq \vert S \vert $ for all $S \subseteq V$. (For any set $S$ of vertices in $G$ we define the neighbor set $N(S)$ of $S$ in $G$ to be the set of all vertices adjacent to vertices in $S$.) Also give an example to show that the above statement is invalid if the condition that the graph be bipartite is dropped.
Let $X\uplus Y = V$ be the bipartition of $G$.
- $(\Leftarrow)$ Any $S\subseteq V$ in particular means any $S\subseteq X$ and any $S\subseteq Y$.
- $(\Rightarrow)$ Perfect matching is both $X$-saturating and $Y$-saturating, so the Hall's condition works for both sides. Apply Hall's theorem two times for $S\cap X$ and $S \cap Y$ and you are done (why $N(S\cap X)$ and $N(S\cap Y)$ are disjoint?).
I hope it helps $\ddot\smile$