Let $G=(V=X \cup Y,E)$ be a bipartite graph.Show that G has a matching which matches every vertex of X. I have a similar question to this on my test tomorrow. Any help towards this question will help
Let $G=(V=X \cup  Y,E)$ be a bipartite graph. Suppose that the degree of each vertex d(v)≥1. Assume also that for each edge xy with x∈ X, we have d(x)≥d(y). Show that G has a matching which matches every vertex of X. 
Hint. It is enough to show that Hall's condition holds on the X-side, since if a
matching has an unmatched X-vertex, we can then use our algorithmic proof of
Hall's Theorem to make it larger (and saturating one extra vertex of X)
 A: We want to show that for every $S \subseteq X$, $\lvert N(S) \rvert \geq \lvert S \rvert$, where $N(S)$ denotes the neighborhood of $S$.
Let $S \subseteq X$ be a minimal counterexample.  This means that for every $x \in S$, $S \setminus \{x\}$ satisfies Hall's condition.  Choose $x \in S$ and let $S' = S \setminus \{x\}$.
First, we may assume that $N(x) \subseteq N(S')$.  If not, let $y$ be a neighbor of $x$ not in $N(S')$.  Then, by hypothesis, we may match all of the elements of $S'$ to elements of $N(S')$ and may also match $x$ to $y$.  Furthermore, we may assume that $\lvert N(S') \rvert = \lvert S' \rvert$: otherwise, we have
$$\lvert N(S) \rvert \geq \lvert N(S') \rvert \geq \lvert S' \rvert + 1 = \lvert S \rvert.$$
Now we match every element $z$ of $S'$ to an element $y$ of $N(S')$.  By our hypothesis that $d(z) \geq d(y)$, we have
$$\sum_{y \in N(S')} d(y) \leq \sum_{z \in S'} d(z) \leq \bigl\lvert E\bigl(S', N(S')\bigr) \bigr\rvert \leq \sum_{y \in N(S')} d(y),$$
that is,
$$\sum_{y \in N(S')} d(y) = \bigl\lvert E\bigl(S', N(S')\bigr) \bigr\rvert.$$
This means that all of the neighbors of the elements of $N(S')$ are in $S'$, which contradicts our hypothesis that $d(x) \geq 1$.  Hence, $S$ cannot be a counterexample, and $X$ satisfies Hall's condition.
