Infinite hall's theorem

Question

If $G=(U,V,E)$ is an Infinite bipartite then Hall's condition is a necessary condition for there to be a matching saturating $U$. However this condition is not sufficient in this Infinite case.

If however there was also a matching saturating $V$ then by the Schröder-Bernstein theorem would this imply that there is a perfect matching between $U$ and $V $?

Answer 1

A standard counterexample to Hall's theorem for infinite graphs is given below, and it actually also applies to your situation:

Here, let $U = \{u_0, u_1, u_2, \dots\}$ be the bottom set of vertices, and let $V = \{v_1, v_2, v_3, \dots\}$ be the top set of vertices. There is an edge $u_0v_i$ for all $i \ge 1$, and an edge $u_i v_i$ for all $i \ge 1$. Then:

• Hall's condition holds for $U$: for any $S \subseteq U$, if $u_0 \in S$, then $N(S) = V$ and so $|N(S)| \ge |S|$. If $u_0 \notin S$, then $N(S)$ contains $v_i$ for every $u_i \in S$, and so $|N(S)| \ge |S|$.
• Actually, Hall's condition also holds for $V$: for any $S \subseteq U$, $N(S)$ contains $u_i$ for every $v_i \in S$ (as well as $u_0$), and so $|N(S)| \ge |S|$. This follows from the second thing you asked for, which is that...
• There is a matching saturating $V$: the matching $\{u_1v_1, u_2v_2, u_3v_3, \dots\}$.

However, there is no matching saturating $U$ (and therefore no perfect matching between $U$ and $V$). No matter which vertex $v_i \in V$ is matched to $u_0$, the corresponding vertex $u_i \in U$ ends up being left out.

Answer 2

A complete matching on $U$ saturating $V$, as I understand the terms, is one-to-one function $f$ from $U$ onto $V$. Then $f$ is a bijection, or a perfect matching. There's no need for the Schröder-Bernstein theorem that I see.

Schröder-Bernstein says that if we have injections $f:A\rightarrow B$ and $g:B\rightarrow A$ then there is a bijection between $A$ and $B$. But in this case, we know that $g=f^{-1}$ so $f$ is itself a bijection.