---

Statement

Problem 9 (printed p. 226). Let $G$ be a graph and $A$, $B$ two disjoint independent sets of $G$. A set $S$ separates $A$ from $B$ if every path joining a vertex of $A$ to a vertex of $B$ passes through a vertex of $S$. Erdős's old conjecture states that $S$ can be chosen so that through every vertex of $S$ there is a path joining $A$ and $B$, these paths being vertex disjoint.

The print records that for $|S|<\aleph_0$ this is Menger's theorem, that for $|S|=\aleph_0$ the problem "is open and could very well be false", and that Aharoni settled the case of bipartite $G$, the general problem remaining open.

Source. P. Erdős, Some problems on finite and infinite graphs, Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 9, p. 226, PDF p. 4 of the Rényi archive's scan (printed p. $n$ = PDF p. $n-222$), read on the rendered page image. The edition read is identified in the source digest.

Read depth. Claims checked: the item was read clause by clause on the page image. It cites Aharoni's result without reference or proof.

Proof pointer

None in the source.

Dependencies

None.

Bears on

• Problem 599: the conjecture is this problem's question. The paper records Menger's finite case and Aharoni's bipartite case, and no result on the general question.