Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a bipartite graph, with bipartition $(X,Y)$ with no isolated vertices. Suppose that for every edge $xy$ with one end $x\in X$ and another end $y\in Y$, we have $\deg(x) \ge \deg(y)$. Prove that $G$ has a matching that covers $X$.

I think I am supposed to apply Hall's Theorem here? The problem is, how would I show that $|N(X)| \ge |X|$ where $|N(X)|$ is the set of neighbours of the vertices of $X$.

share|cite|improve this question
up vote 8 down vote accepted

$$ |X|=\sum_{\langle x,y\rangle\in E}\frac1{\deg(x)}\le\sum_{\langle x,y\rangle\in E}\frac1{\deg(y)}=|Y|\;. $$

share|cite|improve this answer
Beautiful, once I realized how you were doing the counting. (I think that it would be little easier if you wrote $\sum\limits_{\langle x,y\rangle\in E(G)}$ or the like.) – Brian M. Scott Oct 18 '12 at 13:46
@Brian: I guess I was too enamoured with the simplicity and didn't want to clutter it -- I've added an $E$ now as a compromise :-) – joriki Oct 18 '12 at 14:04
Works for me! $\,$ – Brian M. Scott Oct 18 '12 at 14:09
Sorry, how did you come up with the formula, $$\sum_{\langle x,y\rangle\in E}\frac1{\deg(y)}=|Y|\;. $$ – Heisenberg Oct 18 '12 at 14:24
@Heisenberg: Do you literally mean how I came up with it, or how it can be proved? Every $y\in Y$ occurs $\deg(y)$ times in the sum and so contributes $\deg(y)/\deg(y)=1$. How I came up with it is hard to say; I think I thought something along the lines that if we want to compare the sets then we should count them using the edges because that's what links them, and then we have to divide by the degrees to avoid overcounting, and then I saw that we can use the given inequality to go from dividing through the one degree to dividing through the other degree. – joriki Oct 18 '12 at 14:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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