Partition a bipartite graph to a complete matching and an independent set

Question

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.

Answer 1

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.