Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. B. Bollobás, On graphs with at most three independent paths connecting any two vertices, Studia Sci. Math. Hungar. 1 (1966), 137--140 (zbMATH Zbl 0144.23301; dated by the volume's year, which names this page). The paper is not held, no online copy of it is known, and the zbMATH record carries no review. Its result is known through the refereed papers that report it: Leonard (J. Combinatorial Theory Ser. B 13 (1972), p. 242, card) gives k4(n)=2n−1k_4(n)=2n-1 for the least number of edges forcing two points joined by four paths sharing only their ends, citing this paper, and recalls on p. 245 its characterization of the extremal graphs, all of whose blocks are wheels; Leonard 1973 (Period. Math. Hungar. 3, p. 281) reports that the conjecture was verified for m=4m=4 by Bollobás; Sørensen and Thomassen (J. Combinatorial Theory Ser. B 17 (1974), p. 143) report the case as well; and Erdős's 1967 seminar paper (p. 57) credits Bollobás with it. At the parameters of Problem 915 with m=4m=4, k4(3n+1)=6n+1=1+n(42)k_4(3n+1)=6n+1=1+n\binom42, the conjectured value, the guess of Bollobás and Erdős 1962. Leonard (1972, p. 244) observes that the edge-disjoint threshold equals k4k_4, so the answer is yes under either reading. The claim value is proved.

Covers. The case m=4m=4, for every n≥1n\ge1, under the vertex-disjoint reading and hence the edge-disjoint one.

Depends on. Leonard's remark of p. 244, for the edge-disjoint consequence.

Acceptance. Refereed: published in Studia Scientiarum Mathematicarum Hungarica, cited with its venue above. The site credits Bollobás with k4k_4 in its commentary, but its SOLVED label rests on the disproof for m≥5m\ge5, so the credit does not settle this part and reviewed is not listed. The text is not held, so its statement rests on the reports named above and no proof step is checked.