Menger’s theorem for infinite graphs

By R. Aharoni, Eli Berger. 2005

94 citations recorded by the source corpus.

We prove that Menger’s theorem is valid for infinite graphs, in the following strong version: let A and B be two sets of vertices in a possibly infinite digraph. Then there exist a set $\mathcal{P}$ of disjoint A–B paths, and a set S of vertices separating A from B, such that S consists of a choice of precisely one vertex from each path in $\mathcal{P}$. This settles an old conjecture of Erdős.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/71d6e0eb4006042dd508504470a2869137ddf826