Matchmaker's problem This is a past exam exercise I'm unable to solve. 
$B$ is finite set.
$h:B\rightarrow \mathcal{P}(G)$ where $\mathcal{P}(G)$ is the powerset of $G$ with the following properties:


*

*for every $x\in B$, $h(x)$ is a finite subset of $G$

*$X\subseteq B\rightarrow |X|\leq|\cup \{h(x):x\in X\}|$


I would like to prove that there exists a monomorphism $f:B\rightarrow G$ such that
$(\forall x\in B)[f(x)\in h(x)]$.
Is this known as "the matchmaker's problem?"
Thank you very much for your time and effort.
 A: This is known as Hall's theorem. Here is a proof by induction on $|B|.$ The theorem is trivial if $B=\emptyset,$ so we assume that $|B|\ge1.$ For $X\subseteq B$ define $h(X)=\bigcup\{h(x):x\in X\}.$ Define a "critical set" to be a set $C\subseteq B\ $ such that $|C|=|h(C)|, C\ne\emptyset,$ and $C\ne B.$ We consider two cases, depending on whether or not there is a critical set.
Case I. There is no critical set. In other words, $|X|\lt|h(X)|$ whenever $\emptyset\ne X\subsetneq B\ $. Choose $b\in B$ and $g\in h(b)$. Let $B'=B\setminus\{b\}$, and define $h':B'\to\mathcal P(G)$ by setting $h'(x)=h(x)\setminus\{g\}\ $ for $x\in B'$. Then conditions 1 & 2 hold with $B$ and $h$ replaced by $B'$ and $h'$. By the induction hypothesis, there is an injection $f':B'\to G$ such that $f'(x)\in h'(x)$ for all $x\in B'.$ Now the function $f=f'\cup\{(b,g)\}$ does the job.
Case II. There is a critical set. I.e., there is a set $C$ such that $\emptyset\ne C\subsetneq B$ and $|C|=|h(C)|.$ By the induction hypothesis, there is an injection $f_C:C\to G$ such that $f_C(x)\in h(x)$ for all $x\in C$. Let $B'=B\setminus C$. Define $h':B'\to\mathcal P(G)$ by setting $h'(x)=h(x)\setminus h(C)$ for $x\in B'.$ Then conditions 1 & 2 hold with $B$ and $h$ replaced by $B'$ and $h'$. By the induction hypothesis, there is an injection $f':B'\to G$ such that $f'(x)\in h'(x)$ for all $x\in B'.$ Now the function $f=f'\cup f_C$ does the job.
