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

  • 1
    $\begingroup$ 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$? $\endgroup$
    – Dorebell
    Nov 16, 2016 at 8:30
  • $\begingroup$ This certainly doesn't happen in general when the graph is not connected - consider $K_{2,2} \sqcup K_{1,1}$. $\endgroup$
    – Dorebell
    Nov 16, 2016 at 10:05
  • 1
    $\begingroup$ @Dorebell Thanks. I corrected my proof. $\endgroup$ Nov 16, 2016 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.