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

## 1 Answer

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

• Why does the hypothesis that for each edge $e = (x,y)$, $\deg(x) \geq \deg(y)$ imply that the minimum degree in $X$ is greater than the maximum degree in $Y$? Nov 16, 2016 at 8:30
• This certainly doesn't happen in general when the graph is not connected - consider $K_{2,2} \sqcup K_{1,1}$. Nov 16, 2016 at 10:05
• @Dorebell Thanks. I corrected my proof. Nov 16, 2016 at 11:40