Problem Statement
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$?
Categories:
Graph Theory Set Theory
Progress
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].
Source: erdosproblems.com/599 | Last verified: January 15, 2026