Let $G$ be a bipartite graph with bipartition $(X, Y)$ such that $\delta(v)\geq 1$ for every $v\in V(G)$ and whenever $xy$ is an edge of $G$, with $x\in X$ and $y\in Y$, we have $\delta(x)\geq\delta(y)$. Prove that there is a matching that saturates $X$.
I have tried to use Hall's theorem; one easily reduces this problem to showing that under the same conditions, $|X|\leq |Y|$. However I haven't been able to do this. Any help?
Assign a weight of $w(xy):=\frac1{\delta(y)}$ to each edge $xy$. Then the total weight is $$\sum_{xy\in E}w(xy)=\sum_{y\in Y}\sum_{x\in Nb(y)}w(xy)= \sum_{y\in Y}\sum_{x\in Nb(y)}\frac1{\delta(y)}=\sum_{y\in Y}1=|Y|.$$ But it is also $$\sum_{xy\in E}w(xy)=\sum_{x\in X}\sum_{y\in Nb(x)}w(xy)= \sum_{x\in X}\sum_{y\in Nb(x)}\frac1{\delta(y)}\ge \sum_{x\in X}\sum_{y\in Nb(x)}\frac1{\delta(x)}=\sum_{x\in X}1=|X|.$$ Hence $$|X|\le |Y|.$$