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$.
Best Answer
$$ |X|=\sum_{\langle x,y\rangle\in E}\frac1{\deg(x)}\le\sum_{\langle x,y\rangle\in E}\frac1{\deg(y)}=|Y|\;. $$