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?

Source: erdosproblems.com/915

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

SOLVED, the site's label, which attaches to one reading of the ambiguous wording: under the vertex-disjoint reading the answer is no for every $m\ge5$ , and under the edge-disjoint reading the answer is yes for every $m\ge2$ . The site's curator wrote in the thread (28 October 2025) that the question as stated had been disproved for every $m\ge5$ and that the problem was therefore marked solved, having written the day before of leaning toward leaving it open, since calling a false statement solved seemed against the spirit of the question. The standing derived from the claim pages departs from that label: it is disproved, not a bare answer, because the page reads the wording as vertex-disjoint, the source's reading (Formulation), and under that reading accepted full claims disprove the statement; the edge-disjoint reading is proved and is recorded as a variant. The vertex-disjoint reading's status-defining text is Sørensen and Thomassen's paper ([SoTh74]), which proves $k_5(n)=\lfloor\frac83n\rfloor-3$ for $n\ge6$ , $n\ne7$ , $n\ne12$ (Theorem 4, p. 158) and $k_m(n)>\frac{m(m-1)-2}{2m-3}(n-m)$ for infinitely many $n$ for each $m\ge5$ (Corollary 2(a), p. 156), which the paper says "disproves the conjecture of Bollobás and Erdös for all $k\ge5$ " (p. 144). Leonard's counterexample for $m=5$ ([Le73], Period. Math. Hungar. 3 (1973), 281--284) is a graph $G$ with $57$ points and $141$ edges and no two points joined by five internally disjoint paths (pp. 281--282), and for every integer $s$ graphs with $n$ points and more than $[5n/2]+s$ edges and no such pair (pp. 282--283). The other vertex-disjoint text, Mader's $k_m(n)>\frac m2n+C$ for $m\ge6$ ([Ma73], Math. Z. 131 (1973), 223--231): the examples of pp. 228--229 give, in the site's letters, graphs on $N$ vertices with $\frac m2(N-1)+j(\frac m2-2)$ edges for odd $m\ge5$ , or $\frac m2(N-1)+j(m-5)$ edges for even $m\ge6$ , $j$ the number of cut cliques, and no two vertices joined by $m$ internally disjoint paths, so that no constant $C$ makes $\frac m2N+C$ edges force such a pair; both papers are reported as citations in [SoTh74]'s introduction (p. 143). The edge-disjoint reading's status-defining text is Satz 1 of [Ma73] (p. 223) with its Korollar (p. 226), which gives $\ell_m(n)=\lfloor\frac m2(n-1)+1\rfloor$ for every $m\ge2$ , as the site and the thread's reading of the German original state it. What the primary texts establish: the case $m=3$ (Bártfai 1960 and Bollobás and Erdős 1962, $k_3(2n+1)=3n+1$ , the problem's exact parameters, true under either reading); under the vertex-disjoint reading, the exact $k_5(n)$ and the disproof for every $m\ge5$ ([SoTh74], above) with Leonard's counterexample at $m=5$ ([Le73], above) and Mader's examples for every $m\ge5$ ([Ma73], above); and, under the edge-disjoint reading, every $m\ge2$ (Satz 1 and the Korollar of [Ma73], above), with the earlier cases $m=5$ (Leonard's $\ell_5(2n)=5n-2$ , $\ell_5(2n+1)=5n+1$ , [Le72]) and $m=6$ (Leonard's $\ell_6(n)=3n-2$ , [Le73b]), and [Le72]'s observation that $\ell_m(n)=k_m(n)$ for $m\le4$ , so the two readings agree there. The standing targets the vertex-disjoint reading, the source's reading (Formulation), which the curator's post of 28 October 2025 and the formal-conjectures statement also take; under it the question asks whether the statement holds for every $m\ge2$ and $n\ge1$ , and a counterexample at one pair $(m,n)$ refutes it. The claim pages are Leonard (the first published counterexample, at $m=5$ , $n=14$ ), Sørensen and Thomassen (the exact $k_5(n)$ and the disproof for every $m\ge5$ ) and Mader (the examples for every $m\ge5$ , and the edge-disjoint variant proved with its exact threshold), each an accepted full disproof on the refereed publication and the site's acceptance, and the accepted partial claims of Bártfai ( $m=3$ ) and Bollobás ( $m=4$ ), each proved on its refereed publication. Leonard's $\ell_5$ [Le72] and $\ell_6$ [Le73b] answer only the edge-disjoint variant and settle no instance of the targeted reading, so they are recorded as variant results, not claims. The frontmatter is derived from the claim pages; the edge-disjoint reading is recorded as a variant, true for every $m\ge2$ , on Mader's page and under Status support. The site's label is read as attached to one reading of an ambiguous wording, not as a defective one, since each reading is a meaningful question with a settled answer.

Er67b: Erdős, P., Extremal problems in graph theory. A Seminar on Graph Theory, Holt, Rinehart and Winston, New York (1967), 54--59; the site cites "p. 4", the copy's page. The conjecture, its extremal example as printed and Bollobás's $m=4$ result, printed pp. 56--57 = pp. 3--4 of the re-typeset archive copy. Library home: Erdős 1967; paged at Erdős 1967, Conjecture (pp. 56–57 = copy pp. 3–4).
BoEr62: Bollobás, B. and Erdős, P., Gráfelméleti szélsőértékekre vonatkozó problémákról (On extremal problems in graph theory). Mat. Lapok 13 (1962), 143--152 (in Hungarian). The definition of $k_r(n)$ and the theorem $k_3(n)=f(n)$ , pp. 143--144; the guess $k_4(3n+1)=6n+1$ with its example, p. 144. Library home: Bollobás 1962 (a scan, with the library's translation); paged at Bollobás 1962, Theorem (pp. 143–144) and Bollobás 1962, Conjecture (p. 144).
Ba60: Bártfai, P., Solution of a problem posed by P. Erdős (the site's title; the solution of Problem 10 of the 1959 Schweitzer competition, in Hungarian). Mat. Lapok 11 (1960), 175--176. Library home: Bártfai 1960 (read in the 404-page volume scan, pp. 177--178); paged at Bártfai 1960, Solution of Problem 10 (pp. 175–176).
Bo66: Bollobás, B., On graphs with at most three independent paths connecting any two vertices. Studia Sci. Math. Hungar. 1 (1966), 137--140. The case $m=4$ , $k_4(n)=2n-1$ , per the site and [Er67b]. Not held; no online copy known, and a thread post of 27 October 2025 reports the paper as hard to find.
Le72: Leonard, John L., On graphs with at most four line-disjoint paths connecting any two vertices. J. Combinatorial Theory Ser. B 13 (1972), 242--250, doi:10.1016/0095-8956(72)90059-7 (Crossref record accessed). The definitions of a point and a line $r$ -way, p. 243; the definition of $l_r(n)$ with $l_r(n)=k_r(n)$ for $r=2,3,4$ , p. 244; the $J$ -graphs, pp. 245--246; the Theorem, pp. 246--247; the conclusion $l_5(2n)=5n-2$ , $l_5(2n+1)=5n+1$ and the general formula with its open question, p. 250. Library home: Leonard 1972; paged at Leonard 1972, Remark (p. 244) and Leonard 1972, Theorem (pp. 246–247).
Le73: Leonard, John L., On a conjecture of Bollobás and Erdős. Period. Math. Hungar. 3 (1973), no. 3--4, 281--284, doi:10.1007/BF02018594 (Crossref record accessed). The conjecture, the definition of an $m$ -way and the two announced results, p. 281; the framework $F$ and the constructions $F_1$ , $F_2$ , $F_3$ and the counterexample $G$ with $57$ points and $141$ edges, pp. 281--282; the graphs $F_4$ , $F_5$ and $F_6$ with the excess $12k+2$ over $\frac52$ times the number of points, pp. 282--283; the suspicion that the edge-disjoint form holds and the Added in proof, p. 283. Library home: Leonard 1973; paged at Leonard 1973, Counterexample (pp. 281–282) and Leonard 1973, Bound (pp. 282–283).
Le73b: Leonard, John L., Graphs with 6-ways. Canadian J. Math. 25 (1973), no. 4, 687--692, doi:10.4153/CJM-1973-069-x (Crossref record accessed). The Theorem, p. 688. Library home: Leonard 1973; paged at Leonard 1973, Theorem (p. 688).
Ma73: Mader, W., Ein Extremalproblem des Zusammenhangs von Graphen. Math. Z. 131 (1973), no. 3, 223--231, doi:10.1007/BF01187240 (Crossref record accessed). The introduction with its report of the cases $m=4$ , $5$ and $6$ , the notation and Satz 1 (edge-disjoint paths), p. 223; the Korollar with the exact threshold and its extremal graphs, pp. 226--227; the vertex-disjoint examples with no constant $c_n$ , pp. 228--229; Satz 2 under a girth hypothesis, p. 229. Library home: Mader 1973; paged at Mader 1973, Satz 1, Mader 1973, Korollar and Mader 1973, Examples (pp. 228–229).
SoTh74: Sørensen, Bo Aagaard and Thomassen, Carsten, On $k$ -rails in graphs. J. Combinatorial Theory Ser. B 17 (1974), no. 2, 143--159, doi:10.1016/0095-8956(74)90082-3 (Crossref record accessed). The definition of a $k$ -rail and of $f_k(n)$ , the site's $k_m(n)$ , with the conjecture and the reports on Bollobás, Leonard and Mader, pp. 143--144; Theorem 3, the bound $\frac52(n-1)$ for 3-connected graphs, p. 149, with its sharpness Remark, p. 154; Corollary 2, the general lower bound, p. 156; Theorem 4, $f_5(n)=[\frac83n]-3$ for $n\ge6$ , $n\ne7$ , $n\ne12$ , with $f_5(7)=16$ and $f_5(12)=28$ , p. 158 (PDF pp. 1--2, 7, 12, 14 and 16 of the publisher's open-archive file). Library home: Sorensen and Thomassen 1974 (the publisher's open-archive file); paged at Sorensen and Thomassen 1974, Theorem 3, Sorensen and Thomassen 1974, Corollary 2 and Sorensen and Thomassen 1974, Theorem 4.

Problem 915

Status

Proof claims

Discussion