Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. What does it mean to say that $G$ contains a matching from $X$ to $Y$ ? State and prove Hall's Marriage Theorem.

Suppose now that every $x \in X$ has $d(x) \geqslant 1$, and that if $x \in X$ and $y \in Y$ with $x y \in E(G)$ then $d(x) \geqslant d(y)$. Show that $G$ contains a matching from $X$ to $Y$.