Erdős problem #1016 — wave w029

Access date: 2026-07-29 UTC.

Claim labels used below:

• (a) elementary-rigorous: proved here from elementary facts.
• (b) rigorous-modulo-named-theorem/source: a literature or live-page claim, with the source named.
• (c) plausible/structural-unverified: not used as a theorem.
• (d) computational-only: established by the supplied finite computation, not promoted to a uniform theorem.

0. Mandatory live-page check

I fetched both the live problem page and its discussion thread through the Bright Data browser path, rather than datacenter curl.

Live status:

• OPEN.
• 0 claimed proofs.
• “Interested in collaborating”: None.
• “Currently working on this problem”: None.
• Every other displayed marker (“likes,” “looks difficult,” “looks tractable,”

and both formalisation markers) is also None.

• The page was last edited 27 December 2025.
• There is one comment, by TerenceTao at 00:50 on 18 October 2025.

Thus the mandatory stop condition does not apply.

Verbatim live statement

Let \(h(n)\) be minimal such that there is a graph on \(n\) vertices with \(n+h(n)\) edges which contains a cycle on \(k\) vertices, for all \(3\leq k\leq n\). Estimate \(h(n)\). In particular, is it true that \[ > h(n) \geq \log_2n+\log_*n-O(1), > \] where \(\log_*n\) is the iterated logarithmic function?

Results and comment listed on the live page

(b) The page calls these graphs pancyclic and records Bondy's claimed, detail-free bounds

It says Erdős believed the upper bound was closer to the truth but could not prove \(h(n)-\log_2n\to\infty\). It attributes a proof of the displayed lower bound to Sean Griffin (2013) and the first published proof of the upper bound to Chapter 4.5 of George–Khodkar–Wallis (2016).

(c) The sole comment is explicitly covered by the site's warning that comments are unverified. It says that Bondy stated the slightly weaker \(n-1\) lower-bound form without proof; mentions a possibly equivalent 1994 result of Shi; reports two bounds and the conjecture from a hard-to-obtain 1996 paper of Jia; points to George–Khodkar–Wallis for the upper bound; and says the Bondy bounds remain the consensus state of the art apart from small \(n\). It also says the main page was updated in response. I do not use any unverified assertion from this comment.

1. Primary-source check

The following sources were actually located and checked.

1. (b) J. A. Bondy, “Pancyclic graphs I,” J. Combinatorial Theory B 11 (1971), 80–84, DOI 10.1016/0095-8956(71)90016-590016-5), exists and introduces the same notion. The full text was blocked in this environment, so claims about its unproved final bounds are taken from the live page and the modern primary source below, not from an imagined inspection.

1. (b) Sean Griffin, “Minimal Pancyclicity,” arXiv:1312.0274 (2013), exists. Its Table 1 gives exact \(m(n)=n+h(n)\) through \(n=37\). In particular it gives \(h(n)=5\) for \(25\le n\le37\). Its five-chord construction explicitly covers lengths \(3,\ldots,19\) and \(n-17,\ldots,n\), which meet through \(n=37\).

1. (b) J. C. George, A. Marr, and W. D. Wallis, “Minimal Pancyclic Graphs,” JCMCC 86 (2013), 125–133, exists. The paper analyzes chord patterns and, at publication, ends its exact list at \(n=22\).

1. (b) J. C. George, A. Khodkar, and W. D. Wallis, Pancyclic and Bipancyclic Graphs, SpringerBriefs in Mathematics (2016), DOI 10.1007/978-3-319-31951-3, exists; “Minimal Pancyclicity” is Chapter 4, pp. 35–47. I verified the bibliographic record but did not have full-text access to recheck every line of that chapter.

1. (b) Y. Alon and M. Krivelevich, “Sparse pancyclic subgraphs of random graphs”, dated 29 November 2024, exists. Its introduction explicitly states the two Bondy bounds, cites Chapter 4.5 for the upper construction, and says that the exact value within this range is still open. (The site comment calls this a “2023 paper”; the primary PDF currently available is dated 2024.)

1. (c) The comment's Jia citation can be identified through the secondary 2014 survey as X. Jia, “Some extremal problems on cycle distributed graphs,” Congressus Numerantium 121 (1996), 216–222, MR1431994. I did not obtain the primary paper, so I do not rely on the survey's rendering of its formulas.

Targeted searches for “minimal pancyclicity,” “minimum number of edges in a pancyclic graph,” \(m(38)\), \(m(40)\), “five chords,” and post-2024 work found no primary source extending Griffin's exact table past \(n=37\). (c) This is evidence of a literature miss, not a proof of novelty. The exact cases below should therefore be described as “apparently new relative to the located literature.”

2. Elementary lower bound

Write \(m(n)=n+h(n)\).

Lemma (a). A connected graph with \(n\) vertices and \(n+k\) edges has at most

simple cycles.

Proof. Its binary cycle space has dimension

Every simple cycle is a distinct nonzero vector of this space, which has only \(2^{k+1}-1\) nonzero vectors. \(\square\)

A pancyclic \(n\)-vertex graph is connected and needs at least \(n-2\) distinct simple cycles, one for each length \(3,\ldots,n\). With at most four excess edges, the lemma permits at most \(2^5-1=31\) cycles. Therefore

This is (a).

3. A uniform five-chord construction

For \(24\le n\le40\), let the vertices be \(0,1,\ldots,n-1\). Start with the Hamilton cycle

and add these five chords:

Thus \(G_n\) has exactly \(n+5\) edges.

For the certificate below, the same letters \(A,\ldots,E\) denote the fundamental cycles formed by the named chord and the increasing path on \(H\) between its endpoints. Concatenation denotes symmetric difference of edge sets: for example \(CDE=C\mathbin\triangle D\mathbin\triangle E\).

For \(n\ge24\), the relevant endpoints have the fixed cyclic order

Direct cancellation of Hamilton edges shows that every expression in the next two rows is one connected 2-regular subgraph, hence one simple cycle, of the indicated length:

These give every length in

The intervals meet or are adjacent exactly when \(n\le40\). Consequently:

Construction theorem (a).

Combining (1) and (3) proves the main finite result:

Exact theorem (a).

Equivalently:

| \(n\) | 34 | 35 | 36 | 37 | 38 | 39 | 40 | |---:|---:|---:|---:|---:|---:|---:|---:| | \(h(n)\) | 5 | 5 | 5 | 5 | 5 | 5 | 5 | | \(m(n)\) | 39 | 40 | 41 | 42 | 43 | 44 | 45 |

Griffin already records the entries through 37. Thus the substantive additions relative to the located exact table are

4. Independent from-scratch verification

The standalone checker is:

runs/erdos1016_wavew029_reverify.py

SHA-256:

19b34d6b73490f2c3fc59661dd42fcfa4da670481c50e5b2a97ea92e7d3f33f6

Run:

python3 runs/erdos1016_wavew029_reverify.py

It uses only the Python standard library. Its main audit is deliberately independent of the cycle-space method used during discovery:

1. build the graph directly from (2);
2. enumerate all undirected simple cycles by canonical depth-first search;
3. validate every returned vertex sequence edge-by-edge;
4. check that every length \(3,\ldots,n\) occurs;
5. separately reconstruct and validate every symmetric-difference entry in the two symbolic rows above; and
6. check the lower-bound arithmetic \(n-2>31\) for \(34\le n\le40\).

Observed output summary:

n=34: edges=39, simple_cycles=45, lengths=3..34, missing=[]
n=35: edges=40, simple_cycles=45, lengths=3..35, missing=[]
n=36: edges=41, simple_cycles=45, lengths=3..36, missing=[]
n=37: edges=42, simple_cycles=45, lengths=3..37, missing=[]
n=38: edges=43, simple_cycles=45, lengths=3..38, missing=[]
n=39: edges=44, simple_cycles=45, lengths=3..39, missing=[]
n=40: edges=45, simple_cycles=45, lengths=3..40, missing=[]
PASS: C_n plus the five stated chords is pancyclic for 24<=n<=40; the cycle-space bound proves h(n)=5 for 34<=n<=40.

It also prints an explicit vertex-cycle witness for every length in each of the new cases \(n=38,39,40\). Runtime on this VM was 0.08 seconds with 11.4 MB peak RSS. These runtime and exhaustive-enumeration statements are (d); the symbolic construction and lower-bound proof above are (a) and do not depend on trusting the computation.

The auxiliary discovery search is retained as runs/erdos1016_probe.cpp; it is heuristic and is not part of the proof.

5. Exact remaining wall

(d) The same formula (2) at \(n=41\) has cycles of every required length except 21; the standalone checker recomputes this. That failure is only about this construction, not about all five-chord graphs.

(a) The elementary lower bound gives \(h(41)\ge5\). From \(G_{40}\), adding a new vertex adjacent to both ends of a Hamilton-cycle edge while retaining that edge preserves all old cycle lengths and adds a 41-cycle, giving \(h(41)\le6\). Hence the next exact case is isolated to

Any \(41\)-vertex candidate with excess five can be relabelled as \(C_{41}\) plus five chords. There are

raw chord sets. The dihedral group has order 82, leaving roughly \(2.88\times10^{10}\) generic orbit representatives before stronger pruning. At the measured exploratory evaluator rate of about \(3.5\times10^4\) candidates/second, this is about 18,500 raw core-hours, or about 225 core-hours under an ideal full 82-fold symmetry reduction. I did not run that computation.

For the asymptotic problem, the precise failure of the standard machinery is also visible. The binary cycle-space lemma allows every nonzero vector to be a simple cycle of a new length and therefore gives only

A sufficient missing lemma would say that a Hamilton cycle with \(k\) chords has at most

distinct cycle lengths—equivalently, that simplicity failures and repeated lengths save a factor \(2^{\log_*k-O(1)}\) over the raw \(2^{k+1}\) cycle-space count. Inverting such a bound would yield the requested \(\log_*n\) term. No located source or computation here supplies that uniform collision lemma, so the asymptotic Erdős question remains open.

PROVED: \(h(n)=5\) for every \(34\le n\le40\) via an explicit five-chord family; the cases \(n=38,39,40\) extend the verified published exact table through \(n=37\), while the asymptotic problem remains open.