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.