A Cantor-Bernstein Theorem for Paths in Graphs
Reinhard Diestel, Carsten Thomassen · American Mathematical Monthly · 2006
The Cantor-Bernstein theorem says that if for two infinite sets A and B there are injective functions f: A → B and g: B → A then there is a bijection A ↔ B. Perhaps the simplest and most intuitive proof considers the connected components of the bipartite graph whose vertex set is A ∪ B and whose edge set is � { a, f(a) } : a ∈ A � ∪ � { b, g(b) } : b ∈ B �. As every vertex of this graph has one “outgoing ” and at most one “incoming” edge, each of those components is a cycle or an infinite path. In each of these paths and cycles we now select every other edge to mark the desired bijection. The Cantor-Bernstein problem, rephrased as above for graphs, has a natural generalization to paths. Let G be any graph, and let A and B be disjoint sets of vertices in G. Assume that we can find in G a set of disjoint paths from A to B that covers all of A (but not necessarily all of B), and a similar set of disjoint paths from all of B to A. Is there a set of disjoint A–B paths in G that covers both A and B?