Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be minimal such that there is a graph on vertices with edges which contains a cycle on vertices, for all . Estimate . In particular, is it true that
where is the iterated logarithmic function?
Source: erdosproblems.com/1016
A full solution has been claimed but not yet accepted. The statement is true.
The site labels the problem OPEN. What is proved: , with the proof in Griffin's preprint [Gr13] (from Shi's bound on the number of cycles of a Hamiltonian graph with chords). Claimed without a proof in the sources found: , stated by Bondy in 1971 on p. 84 of [Bo71] as for , with "we can prove that" and no proof or indication of one in the paper; the site names Chapter 4 of George, Khodkar and Wallis [GKW16] as the earliest proof in print, whose general upper bounds are Theorem 18, for as printed (its construction is argued for , up to ; at it gives a 21-cycle only at and ), and Theorem 19, on windows of where this reads , with no bound in the form printed (a filing observation, not a review verdict), so the upper bound in the site's form has no proof in any source found. The lower half of the same printed claim is the bound Griffin proves. Erdős's 1971 item 10 reports Bondy's then unpublished bounds as . The site's yes-or-no question is the gap between these two bounds, and no source found closes it or proves even ; the exact values for are known (Griffin's Table 1; [GKW16], pp. 37--42). One full proof claim is pending: a proof-claim tab entry of 2026-09-24 asserting with a write-up and a Lean development, recorded on its claim page (KNT, 2026) as claimed, unreviewed and not built in this corpus. The derived standing, claimed, proved, departs from the site's OPEN only by counting this pending claim, which no outside review has accepted; it becomes solved, proved if the claim is accepted. No proof, disproof or preprint was found in the search whose scope the Current assessment records, which predates the claim; this is a bounded negative finding, not a certificate of openness.