Let $G$ a bipartite graph with partitions $X$, $Y$ such that all degrees in $X$ are at least one, and if $x\in X$ has an edge to $y$ then $d(x)\geq d(y)$.
Show that there's a matching saturating X.
I think I need to use Hall's theorem, but my attempts to show Hall's condition holds for such graphs always ended up in cyclic arguments.
Also, I've noted that if $k$ vertices from $X$ share a neighbour, their neighbourhood has size at least $k$ (the neighbour has degree $\geq k$, thus all of the vertices have degree at least $k$), yet I'm not sure how to use it to show Hall's condition in general.
(Note: this is not the same question as this one, as here we have $d(x)\geq d(y)$ guaranteed only if $x$ has an edge to $y$)
Let $A$ be a subset of $X$, denote the neighbourhood of $A$ by $B$.
Consider the graph induced by $A$ and $B$.
The sum over every edge $\{a,b\}$ in the graph of $\frac{1}{\deg(a)}$ gives us the number of vertices in $A$.
The sum over every edge $\{a,b\}$ in the graph of $\frac{1}{\deg(b)}$ gives us the number of vertices in $B$.
The second sum is larger than the first because the summand corresponding to each edge is larger in the second sum.