Matching in a bipartite graph saturating $X$ Let $G$ be a bipartite graph with bipartitions $X, Y$ . Suppose $X$ has no isolated vertices (i.e., vertices with degree $0$) and for all $(x,y) ∈ E$ with $x ∈ X$, $y ∈ Y$, $degree(x) ≥ degree(y)$. Prove that $G$ has a matching that saturates $X$.
 A: I'll assume that we deal with a simple finite undirected graph. As far I understood your question, we have to prove there exists a matching containing each vertex of $X$. For this purpose 
we’ll use Hall marriage theorem,
(see also this thread for its different proofs). We can apply the theorem, because $|X’|\le |N(X’)|$ for any subset $X’$ of $X$.
Indeed, assume the converse. Let $X’$  be a subset of $X$ of smallest size such that $|X’|>|N(X’)|$. Let $G’$ be the subgraph induced by vertices $X’\cup N(X’)$. Let $Y^*$ be an arbitrarily subset of $N(X’)$ and $X^*$ be the neighborhood of the set $Y^*$ in the graph $G’$. If $|Y^*|>|X^*|$ then 
$$|X’|>|X’\setminus X^*|=|X’|-|X^*|>|N(X’)|-|Y^*|\ge |N(X’\setminus X^*)|,$$
which contradicts the minimality of the set $X’$. Thus $|Y^*|\le |X^*|$ and by Hall marriage theorem 
there exists a matching $M$ of the graph $G’$ containing each vertex of $N(X’)$. Since $|X’|>|N(X’)|$, there exists an unmatched vertex $x’\in X’$. Since the vertex $x’$ is not isolated, $\deg x’>0$. But 
$$\sum_{x\in X’} \deg x\le  \sum_{y\in N(X’)} \deg y=\sum_{(x,y)\in M} \deg y\le \sum_{(x,y)\in M} \deg x\le \sum_{x\in X’} \deg x -\deg x’,$$ 
a contradiction. Thus $|X’|\le |N(X’)|$. Hence by Hall marriage theorem there exists a matching containing each vertex of $X$.
