Claims

../

1960_01_01_bartfai: Bártfai's solution (Mat. Lapok 1960) shows that a graph on 2n+1 vertices with 3n+1 edges has an even cycle through a theta subgraph, which gives two vertices joined by three internally disjoint paths: the case m = 3.

1966_01_01_bollobas: Bollobás (Studia Sci. Math. Hungar. 1966) proves that 2n − 1 edges on n vertices force two vertices joined by four internally disjoint paths, so k_4(3n+1) = 6n+1: the case m = 4, under either reading.

1973_09_01_leonard: Leonard (Period. Math. Hungar. 1973) gives a graph with 57 vertices and 141 edges, the problem's parameters at m = 5 and n = 14, with no two vertices joined by five internally disjoint paths: the first published disproof.

1973_09_01_mader: Mader (Math. Z. 1973) proves the edge-disjoint Bollobás–Erdős conjecture for every m with the exact threshold and refutes the vertex-disjoint form for every m at least 5; the one result answering both readings of the question.

1974_10_01_sorensen_thomassen: Sørensen and Thomassen (J. Combin. Theory Ser. B 1974) determine k_5(n) and prove a lower bound for k_m(n) with slope above m/2 for every m at least 5, refuting the vertex-disjoint reading of the conjecture for every such m.

---