I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:


* Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into 1st and 2nd class citizens. Suppose that Hall's condition is satisfied for 1st class citizens. That is, for every set $M\subset\{\text{1st class boys}\}$ there are at least $|M|$ girls (from both classes) adjacent to $M$. And similarly for every $W\subset\{\text{1st class girls}\}$ there are at least $|W|$ boys adjacent to $W$. Then there exists a matching covering all 1st class citizens.


I need this fact as a lemma in a paper on geometric analysis. The proof is more or less straightforward but it occupies some space when written down. And I suspect that the fact may be well-known to specialists. Is this indeed the case and what are relevant references?



An unfair marriage lemma
In this answer I sketch an easy proof of your lemma and then give some references.


The easy proof uses Knaster's fixed point theorem:


THEOREM. Let $S$ be any set (finite or infinite) and let $\varphi:\mathcal P(S)\to\mathcal P(S)$ be an order-preserving map, i.e., $X\subseteq Y\implies\varphi(X)\subseteq\varphi(Y).$ Then $\varphi$ has a fixed point.


PROOF. Let $X\_0=\bigcup\{X\in\mathcal P(S):X\subseteq\varphi(X)\}.$ It is easy to see that $\varphi(X\_0)=X\_0.$


(Knaster's fixed point theorem was set as a [Putnam Problem in 1957](https://mks.mff.cuni.cz/kalva/putnam/psoln/psol5712.html). The generalization to complete lattices is called the [Knaster-Tarski Theorem](http://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem).)


Now let $B\_1,B\_2,G\_1,G\_2$ be the set of all first-class boys, second-class boys, first-class girls, and second-class girls, respectively; $B=B\_1\cup B\_2,\ G=G\_1\cup G\_2,\ B\_1\cap B\_2=G\_1\cap G\_2=\emptyset.$ By Hall's theorem there are matchings $f:B\_1\to G$ and $g:G\_1\to B.$ Define an order-preserving map $\varphi:\mathcal P(B\_1)\to\mathcal P(B\_1)$ by setting, for $X\subseteq B\_1,$
$$\varphi(X)=B\_1\setminus g[G\_1\setminus f[X]].$$
By Knaster's fixed point theorem we have $\varphi(X\_0)=X\_0$ for some $X\_0\subseteq B\_1$. Now we can match the boys in $X\_0$ with the girls in $f[X\_0]$ and the girls in $G\_1\setminus f[X\_0]$ with the boys in $g[G\_1\setminus f[X\_0]].$


Here are some references related to your lemma:


L. Mirsky, *Transversal Theory*, Academic Press, New York and London, 1971.


L. Mirsky and Hazel Perfect, Systems of representatives, J. Math. Analysis Appl. 15 (1966), 520-568.


O. Ore, *Theory of Graphs*, Amer. Math. Soc. Colloquium Publications No. 38, Providence, 1962 [Theorem 7.4.1].


Here is how your lemma is stated on p. 36 of Mirsky's book:



> 
> THEOREM 2.3.1. *Let $(X,\Delta,Y)$ be a deltoid and let $X',Y'$ be admissible subsets of $X,Y$ respectively. Then there exist linked sets $X\_0,Y\_0$ such that $X'\subseteq X\_0\subseteq X,\ Y'\subseteq Y\_0\subseteq Y.$*
> 
> 
> 


The jargon is defined on pp. 33-34. Namely, a *deltoid* $(X,\Delta,Y)$ is a bipartite graph with partite sets $X,Y$ and edge set $\Delta$; a set $X'\subseteq X$ is *admissible* if there is an injective matching of $X'$ to $Y$; a set $Y'\subseteq Y$ is *admissible* if there is an injective matching of $Y'$ to $X$; two sets $X\_0\subseteq X,Y\_0\subseteq Y$ are *linked* if there is a bijective matching of $X\_0$ to $Y\_0.$


**P.S.** Sergei Ivanov has commented that the result, as stated in the question, can be traced back to Dulmage & Mendelsohn, Some generalizations of the problem of distinct representatives, Canad. J. Math. 10 (1958) 230–241, Theorem 1.


