Logo
All Random Solved Random Open
SOLVED
Let $G$ be a (possibly infinite) graph and $A,B$ be disjoint independent sets of vertices. Must there exist a family $P$ of disjoint paths between $A$ and $B$ and a set $S$ which contains exactly one vertex from each path in $P$, and such that every path between $A$ and $B$ contains at least one vertex from $S$?
Sometimes known as the Erdős-Menger conjecture. When $G$ is finite this is equivalent to Menger's theorem. Erdős was interested in the case when $G$ is infinite.

This was proved by Aharoni and Berger [AhBe09].