# Cantor-Bernstein-Schröder Theorem: small proof using Graph Theory, is this correct?

The theorem:

Suppose there exist injective functions $A \to B$ and $B \to A$ between two inﬁnite sets $A$ and $B$. Then there exists a bijection $A \to B$.

Proof:

Let $f: A \to B$ and $g: B \to A$ be injective functions. Let $G$ be the bipartite and undirected graph with partition sets $A$ and $B$ and edges $ab$ when either $f(a) = b$ or $g(b) = a$ for all $a \in A$ and $b \in B$. Note that $f$ and $g$ each correspond to a matching of $A$ and $B$ respectively. Clearly, if $G$ has a perfect matching (which we'll prove), then there exists a bijection $A \to B$.

Because $f$ and $g$ are injective, each vertex in $G$ has at least degree $1$ and at most degree $2$. Therefore each component $C$ in $G$ is either a path or a cycle. If $C$ is a cycle then, because $G$ is bipartite, it follows that $C$ is even and thus has a perfect matching. On the other hand, if $C$ is a path, it may be finite or infinite. If $C$ is finite, then $C$ must be even, because the injectivity of $f$ and $g$ together imply that $|A \cap C| = |B \cap C|$, and so it has a perfect matching. Otherwise, if $C$ is infinite, then either $C$ has one vertex of degree 1 and all others of degree 2 or has all vertices with degree 2: in the first case we take the odd numbered edges (counting from the one edge incident with the vertex of degree 1) and in the second case we just take alternating edges starting wherever we want.

• The path components are infinite. – confusedStudent Aug 5 '19 at 8:28

This same argument was described by John Conway and Peter Doyle in their 1994 paper, division by three, Section 4, "The Cantor-Schroder-Bernstein theorem". They color the edges red and blue, which helps clarify why the cycles and finite paths are of even size. Another way to help clarify this is to make the edges from $A$ to $B$ and $B$ to $A$ directed.