PROVED
This has been solved in the affirmative.
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].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #599, https://www.erdosproblems.com/599, accessed 2026-01-16
