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.


1 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.

I also co-authored a paper on this problem, some related generalizations and optimization problems, and some applications to fair division.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.