{'fraction_non_alphanumeric': 0.041666666666666664, 'fraction_numerical': 0.007291666666666667, 'mean_word_length': 3.5761904761904764, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Path matchings in infinite graphs

The Cantor-Bernstein theorem says that if for two infinite sets A and B there are injective functions A→B and B→A then there is a bijection A ↔ B. As is well known, this can be rephrased (and very easily proved; see e.g. [ 5 ]) in terms of matchings in bipartite graphs (A, B). Pym [ 3, 4 ] proved the analogous result for disjoint paths between two vertex sets A and B in an arbitrary graph. While the proof in [ 3 ] is quite long, the one in [ 4 ] is short but indirect, applying the Rado Selection Principle to a suitably strengthened finite statement. The purpose of this note is to give a short and direct proof, which does not use the axiom of choice. See [ 2 ] for an even simpler direct proof by transfinite induction. Let us say that a set P of paths in a graph G covers a set U ⊆ V (G) if every vertex in U is the first or the last vertex of some path in P. Any other terms or notation we use can be found in [ 1 ].