I am looking for a reference for the following theorem:Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$).There is a nonempty subset $Y_1 \subseteq Y$, and a partition of $X$ to disjoint subsets $X_1$ and $X_2$, such that:There is a complete matching between $X_1$ and a subset of $Y_1$;There are no edges between $X_2$ and $Y_1$.Intuitively, $X$ can be seen as a set of men and $Y$ can be seen as a set of women. An edge between $x \in X$ and $y \in Y$ means that $x$ and $y$ like each other (like is considered a symmetric relation). The goal is to find a subset of the women ($Y_1$) and a subset of the men ($X_1$), such that each man can marry a woman he likes without upsetting any of the other men ($X_2$), because no unmarried man likes any married woman.This sounds similar to Hall's marriage theorem, but the premise is simpler. And, I am mainly looking for a reference that I can cite.Some special cases:If the graph is full (i.e. any man likes any woman), then we can take $Y_1=Y$, $X_1=X$, $X_2=\phi$.If the graph is empty (i.e. no man likes no woman), then we can take $Y_1=Y$, $X_1=\phi$, $X_2=X$.If there is $y \in Y$ with no neighbours (i.e. a woman that doesn't like any man), then we can take $Y_1={y}$, $X_1=\phi$, $X_2=X$.If there is $y \in Y$ with a single neighbour $x \in X$  (i.e. a woman that likes a single man), then we can take $Y_1={y}$, $X_1={x}$, $X_2=X-{x}$.The question becomes more problematic when all $y \in Y$ have at least two neighbours.
Partition a bipartite graph to a complete matching and an independent set
graph theory;reference request
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)|<|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|<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.