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 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 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 ,
, the conjectured value, the guess of
Bollobás and Erdős 1962.
Leonard (1972, p. 244) observes that the edge-disjoint threshold equals ,
so the answer is yes under either reading. The claim value is proved.
Covers. The case , for every , 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 in
its commentary, but its SOLVED label rests on the disproof for , 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.