---

Claim. P. Bártfai, solution of Problem 10 of the 1959 Schweitzer competition, a problem posed by Erdős, Mat. Lapok 11 (1960), 175--176 (the site's title: Solution of a problem posed by P. Erdős; dated by the volume's year, which names this page). The published solution, a reformulation of the solution the journal credits to Bártfai (solution_p175), proves that every loopless graph with $2n+1$ vertices and $3n+k$ edges, $k\ge1$, contains a self-avoiding closed line with an even number of edges, and that $n$ triangles sharing a vertex show $3n$ edges do not suffice. The proof finds two vertices joined by three internally disjoint paths, a theta subgraph, and picks the even cycle among its three cycles. Bollobás and Erdős (Mat. Lapok 13 (1962), pp. 143--144) state that this proof also gives two vertices joined by three paths sharing only their endpoints, and so $k_3(2n)=3n-1$ and $k_3(2n+1)=3n+1$, crediting Bártfai's proof. At the parameters of Problem 915 with $m=3$, a graph with $1+2n$ vertices and $1+3n$ edges has two vertices joined by three internally disjoint paths, and so also by three edge-disjoint ones. The claim value is proved: the answer at $m=3$ is yes under either reading.

Covers. The case $m=3$, for every $n\ge1$, under the vertex-disjoint reading and hence the edge-disjoint one; nothing for $m\ge4$.

Depends on. [[../library/extremal_graph_theory/bollobas_1962_grafelmeleti_szelsoertekekre_vonatkozo_problemakrol_extremal_problems/theorem_p144|Bollobás and Erdős's theorem $k_3(n)=f(n)$]], which states the three-path consequence of this proof.

Acceptance. Refereed: published in Matematikai Lapok, cited with its venue above. The site credits Bártfai with $k_3$ in its commentary, but its SOLVED label rests on the disproof for $m\ge5$, so the credit does not settle this part and reviewed is not listed. The source has a library source card; the link above is the record of the repository that hosts the volume.