Reused writeup on Math-6070 (gpt pro 5.2)

Erdős Problem 1016 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1016

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1016.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1016.tex.

FORMAL RESTATEMENT. For each integer $n\ge 3$, let $h(n)$ be the minimum integer $h\ge 0$ such that there exists a (simple, undirected) graph $G$ on $n$ vertices with exactly $n+h$ edges and containing a cycle of every length $k$ for $3\le k\le n$. Such a graph is called pancyclic. The task is to estimate $h(n)$; in particular, decide whether \[ h(n)\ge \log_2 n + \log_* n - O(1) \] as $n\to\infty$, where $\log_* n$ is the iterated base-2 logarithm.

QUICK LITERATURE/CONTEXT CHECK. The problem statement reports a claimed lower/upper range of Bondy and later proofs of the displayed bounds, but does not include a full proof in the extracted text.

ATTACK PLAN. Proof track: Convert the edge surplus $h$ into the cycle-space dimension $m-n+1$, which limits the total number of cycles by $2^{m-n+1}$. Since pancyclic graphs require at least $n-2$ distinct cycle lengths, this gives a logarithmic lower bound. Construction track: Build explicit sparse pancyclic graphs starting from a Hamilton cycle and adding chords that force cycles of all lengths.

WORK.

Lemma 1 (cycle-space bound on the number of simple cycles). Let $G$ be a connected graph with $n$ vertices and $m$ edges. Let $r:=m-n+1$ be the dimension of the cycle space of $G$ over $\mathbb{F}_2$. Then the number of distinct simple cycles in $G$ is at most $2^r-1$.

Proof. Consider the vector space $\mathcal{C}(G)\subseteq \mathbb{F}_2^{E(G)}$ of all even subgraphs, i.e. subsets of edges in which every vertex has even degree (equivalently, the cycle space). It is standard (and follows, for example, from choosing a spanning tree and the fundamental cycles) that $\dim \mathcal{C}(G)=r$ and hence $|\mathcal{C}(G)|=2^r$. Each simple cycle $C$ determines a nonzero vector $\mathbf{1}_C\in \mathcal{C}(G)$ (its edge-incidence vector); distinct simple cycles have distinct edge sets, hence distinct vectors. Therefore the number of simple cycles is at most the number of nonzero vectors in $\mathcal{C}(G)$, namely $2^r-1$. $\square$

Corollary 1 (Bondy-type logarithmic lower bound). For all $n\ge 3$, \[ h(n)\ge \left\lceil \log_2(n-1)\right\rceil -1. \] Proof. If $G$ is pancyclic on $n$ vertices with $m=n+h$ edges, then $G$ is connected and has $r=m-n+1=h+1$. A pancyclic graph contains at least one simple cycle of each length $3,4,\dots,n$, so it has at least $n-2$ distinct simple cycles. By Lemma 1, $n-2\le 2^{h+1}-1$, i.e. $2^{h+1}\ge n-1$, which is equivalent to the displayed bound. $\square$

Lemma 2 (a simple explicit pancyclic construction). For every $n\ge 3$ there exists a pancyclic graph on $n$ vertices with $2n-3$ edges. Consequently, $h(n)\le n-3$.

Proof. Label the vertices $v_1,\dots,v_n$. Start with the Hamilton cycle \[ C: v_1v_2,\ v_2v_3,\dots,\ v_{n-1}v_n,\ v_nv_1, \] which has $n$ edges. Add the chords $v_1v_i$ for each $i\in\{3,4,\dots,n-1\}$ (these are not edges of $C$), adding $n-3$ edges in total. Call the resulting graph $G$; it has $n+(n-3)=2n-3$ edges. For each integer $\ell$ with $3\le \ell\le n-1$, the edges \[ v_1v_2,\ v_2v_3,\dots,\ v_{\ell-1}v_{\ell},\ v_{\ell}v_1 \] form a cycle of length $\ell$ (the last edge is the added chord $v_\ell v_1$). For $\ell=n$ the original Hamilton cycle $C$ gives a cycle of length $n$. Thus $G$ contains cycles of all lengths $3\le \ell\le n$, i.e. $G$ is pancyclic. $\square$

FAST REALITY CHECK. Brute force over all graphs on $n\le 7$ vertices gives the exact values: \[ \begin{array}{c|ccccc} n & 3 & 4 & 5 & 6 & 7\\\hline \min\{e(G):G\text{ pancyclic on }n\text{ vertices}\} & 3 & 5 & 6 & 8 & 9\\ h(n)=\min e(G)-n & 0 & 1 & 1 & 2 & 2 \end{array} \]

VERIFICATION. Lemma 1 injects the set of simple cycles into the nonzero elements of the cycle space; this uses only that every simple cycle is an even subgraph and that distinct cycles have distinct edge sets. Lemma 2 explicitly exhibits, for each $\ell$, a cycle and checks that its edges exist in $G$. The brute force check was done by enumerating all labeled graphs for $n\le 7$ and testing existence of cycles of all lengths $3,\dots,n$.

FINAL. UNRESOLVED

(i) Strongest proved partial result: the clean universal bounds \[\left\lceil \log_2(n-1)\right\rceil -1\le h(n)\le n-3,\] plus exact computed values for $n\le 7$.

(ii) First gap (crisp): improve either side to a bound of order $\log n$ (or show $h(n)$ must be super-logarithmic); in particular, bridge the gap between $\Omega(\log n)$ and $O(n)$.

(iii) Top 3 next moves: 1. Strengthen Corollary 1 by proving a substantially smaller upper bound on the number of distinct cycle lengths possible in terms of $h$ (not merely the number of cycles). 2. Improve the construction in Lemma 2 by adding $O(\log n)$ chords to a Hamilton cycle and proving it yields cycles of every length (attempting a binary-representation argument). 3. Extend brute-force computation to $n=8,9,10$ using isomorphism pruning (to guess the growth of $h(n)$).

(iv) Minimal counterexample structure: if the conjectured lower bound $h(n)\ge \log_2 n+\log_* n-O(1)$ is false, then there should exist infinitely many $n$ with a pancyclic graph having $n+\log_2 n+o(\log n)$ edges; such graphs would have cycle-space dimension only about $\log n$, so they must realize nearly all $n-2$ cycle lengths using comparatively few independent cycles.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.