# Application of Hall's Theorem

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

-

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

-
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