Partition a bipartite graph to a complete matching and an independent set
This question was subsequently posted on Math.SE. It received a complete answer by Zur Luria which I am quoting here.

I think I can prove your conjecture using Hall's theorem.
First of all, any perfect matching is also an envy-free matching, so if $G$ satisfies Hall's condition then there is an envy-free matching.
Otherwise let $S \subseteq X$ be a maximal subset such that $|N(S)|&lt;|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|&lt;n$ then the subgraph of $G$ on the vertices$X\smallsetminus S,Y \smallsetminus N(S)$ satisfies Hall's condition (otherwise we can make $S$ larger), and so it has a matching that matches all of the vertices in $X\smallsetminus S$. This matching is envy-free.