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

Solution 1:

Yes, nice work -- the proof is correct. In fact, this proof does not rely on the axiom of choice (although this may not be obvious until you actually sit down and work out the set-theoretic details).

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.

(I don't think that Doyle and Conway are the first to explain the Cantor-Schroder-Bernstein theorem in this way, but you may enjoy the paper more generally.)