Let $G=(X,Y)$ be a bipartite graph, and suppose every $x\in X$ has degree at least 1, and also that whenever $xy\in E(G)$, $d(x)\geq d(y)$. I wish to show that there is a matching from $X$ to $Y$.
I have made small amounts of progress on special cases.
If I induct on $|X|$, then in the case that $d(x)>d(y)$ whenever $x,y\in E(G)$, fixing an edge, deleting it and applying induction gives an inductive step for this special case. Outside the special case, I don't see what to do.
If I assume that whenever $A$ is a subset of $X$, the average degree of vertices in $\Gamma(A)$ is at most that of vertices in $A$, then I think I can finish it off, but I have been struggling to get this inequality out for a long time (if it is true) and cannot proceed with it.
Any hints much appreciated.
EDIT: typo in statement corrected