Hall’s marriage theorem with infinitely many people

bipartite-graphsgraph theory

I fully understand Hall's marriage theorem, if I have $n$ boys and $m$ girls and if every subset of $k$ boys knows at least $k$ girls then there exists a matching between the boys and girls.
What happens if we now consider a village with infinitely many boys and girls? If the marriage condition still holds does Hall's marriage theorem still hold and that there is a matching?

Best Answer

Unfortunately, it does not hold. Let $B=\{b_0,b_1,b_2\ldots\}$ be the set of boys, and $G=\{g_1,g_2,\ldots\}$ be the set of girls, i.e., each number of boys and girls is countably infinite. Assume below conditions:

  • Boy $b_0$ knows every girl, and
  • boy $b_i$ knows girl $g_i$ for all $i \geq 1$.

Then it satisfies Hall's marriage condition. However, there is no matching cover $B$.

I referred: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem

I don't know the infinite Hall's marriage theorem holds if the condition has more restriction: Each boy know only finitely many girls.

Related Question