[Math] Matching in a bipartite graph saturating $X$

Question

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$.

Answer 1

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$.