Erdős Problem #915

Let \(G\) be a graph with \(1+n(m-1)\) vertices and \(1+n\binom{m}{2}\) edges. Must \(G\) contain two points which are connected by \(m\) disjoint paths? A conjecture of Bollobás and Erdős [BoEr62]. This would be the best possible, as demonstrated by \(n\) copies of \(K_m\) which share a single vertex (but are otherwise disjoint). It is unclear whether disjoint here is to mean edge-disjoint or (internally) vertex-disjoint. The above construction is valid for either interpretation. This is the internally vertex-disjoint reading. It is trivial for \(m = 2\), and was proved for \(m = 3\) by Bártfai [Ba60] and for \(m = 4\) by Bollobás [Bo66]. Leonard [Le73] disproved this conjecture for \(m=5\), giving an explicit counterexample with \(57\) vertices and \(141\) edges, and Mader [Ma73] disproved the conjecture in general for all \(m \geq 6\). Sørensen and Thomassen [SoTh74] proved that the conjectured bound of Bollobás and Erdős holds if the graph is \(3\)-connected.