Erdős problem #65 — wave 7d

Access/research date: 2026-07-27 UTC.

Outcome

[d + a] Exact finite theorem. For every

and every simple \(n\)-vertex graph \(G\) with at least \(d(n-d)\) edges,

Equality holds if and only if \(G\cong K_{d,n-d}\). The exhaustive part is computational-only [d]; the passage from the exact edge slice to “at least” and the equality argument are elementary [a].

This verifies the precise integer normalization used in the announced large-\(d\) theorem for all 16 parameter cells through order 10. It does not prove the open problem uniformly in \(n\), does not cover all real edge densities \(k\), and does not turn the unpublished “sufficiently large \(d\)” announcement into an all-\(d\) theorem.

Claim labels used throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the explicitly named theorem/primary source;
• [c] plausible/structural-unverified (including search misses and

cost extrapolations);

• [d] computational-only.

0. Mandatory live-page gate

[b: live-page observation] I fetched both the live problem page and its discussion thread through the Bright Data browser path, rather than datacenter curl.

The live page displayed:

• status: OPEN;
• 0 claimed proofs;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• last edit: 08 February 2026;
• three comments.

Thus none of the requested stop conditions was present.

Verbatim current statement

Let \(G\) be a graph with \(n\) vertices and \(kn\) edges, and \(a_1<a_2<\cdots\) be the lengths of cycles in \(G\). Is it true that \[ > \sum\frac{1}{a_i}\gg \log k? > \] Is the sum \(\sum\frac{1}{a_i}\) minimised when \(G\) is a complete bipartite graph?

Listed results and comments

[b: source report] The page attributes the first question to Erdős and Hajnal and says:

1. Gyárfás–Komlós–Szemerédi proved the \(\gg\log k\) lower bound, so

only the second question remains.

1. Liu–Montgomery proved the asymptotically sharp

\((\tfrac12-o(1))\log k\) lower bound.

1. Montgomery's survey announces forthcoming joint work with

Milojević, Pokrovskiy, and Sudakov giving the exact complete bipartite extremizer for sufficiently large parameter.

[b: source report] The three comments were:

1. ebarschkis, 04 Feb 2026: points to a relevant source; the site says

it was updated in response.

1. JakeMallen, 04 Feb 2026: points to page 8 of Montgomery's survey

and reproduces its announced exact result for every sufficiently large \(d\); the site again says it was updated.

1. StijnC, 05 Feb 2026: observes that proving the remaining small

values can still be difficult, and guesses the statement is true for small \(d\).

[b: checked discrepancy] The main-page prose literally says that the forthcoming work proves the sum is “maximised” by a complete bipartite graph. This conflicts with both the question immediately above it and the linked primary survey, whose page 8 says “minimised exactly.” The discussion comment also quotes “minimised.” I have preserved the discrepancy here rather than silently editing it; all mathematics below uses the minimization formulation in the statement and primary survey.

1. Primary-source check

[b: Gyárfás–Komlós–Szemerédi] In On the distribution of cycle lengths in graphs, J. Graph Theory 8 (1984), 441–462, DOI 10.1002/jgt.3190080402, the authors define

Their Theorem \(4'\) gives \(f(\alpha)\ge c\log\alpha\) above an absolute threshold. This verifies the live page's first listed result.

[b: Liu–Montgomery] Hong Liu and Richard Montgomery, A solution to Erdős and Hajnal's odd cycle problem, JAMS 36 (2023), 1191–1234, DOI 10.1090/jams/1018, arXiv:2010.15802, Corollary 1.2, prove that a graph of average degree \(q\) satisfies

Since the live page's density \(k=|E|/|V|\) has average degree \(2k\), this gives the same asymptotic leading constant in \(\log k\).

[b: Montgomery survey] Richard Montgomery, Cycles and expansion in graphs, EMS Magazine 138 (2025), 5–12, published 29 January 2026, DOI 10.4171/MAG/287, states on page 8 that forthcoming work with Milojević, Pokrovskiy, and Sudakov gives some \(d_0\) such that, for every \(d\ge d_0\), among \(n\)-vertex graphs with at least \(d(n-d)\) edges, \(L(G)\) is minimized exactly by \(K_{d,n-d}\).

[c: honest search miss] Exact-author/title/keyword searches of arXiv and the web did not find a public preprint of that four-author work. Montgomery's current papers and preprints page, checked on the research date, also did not list it. This does not prove that no manuscript exists; it means the announced theorem could not be inspected or used beyond the precise statement in the primary survey. I found no primary source claiming the remaining small-\(d\) cases.

2. Exact normalization and elementary reductions

Let \(\mathcal C(G)\) be the set of distinct simple-cycle lengths in \(G\), and let \(L(G)=\sum_{\ell\in\mathcal C(G)}1/\ell\).

[a] Cycle spectrum of the candidate. Assume \(2\le d\le n/2\). Every cycle in \(K_{d,n-d}\) is even and uses the same number \(j\) of vertices from each part, so its length is \(2j\) with \(2\le j\le d\). Conversely, choosing \(j\) vertices in each part and alternating them produces a \(2j\)-cycle. Hence

The exact values used below are

[a] Exact-edge reduction. Put \(m=d(n-d)\). If \(G\) has at least \(m\) edges, choose any spanning \(m\)-edge subgraph \(H\subseteq G\). Every cycle of \(H\) is a cycle of \(G\), so

It is therefore enough to prove the lower bound on the exact \(m\)-edge slice.

[a, conditional on the exact-slice computation] Equality extension. Suppose the only exact-\(m\) minimizer is \(K_{d,n-d}\), and suppose a graph \(G\) with more than \(m\) edges ties its score. The preceding \(H\) must be \(K_{d,n-d}\). Every additional edge of \(G\) lies inside one of its two parts and, together with any vertex in the opposite part, creates a triangle. This adds a new length 3 and strictly raises \(L\), a contradiction. Thus exact uniqueness implies uniqueness among all graphs with at least \(m\) edges.

[a] The case \(d=1\) is deliberately excluded from the uniqueness claim. Here \(K_{1,n-1}\) is a tree and has score 0, but every \(n\)-vertex tree also ties. This is consistent with the live page's weaker wording “minimised when,” and explains why an “exactly” formulation needs \(d\ge2\).

3. Exhaustive computation

Result

[d] The standalone checker enumerated one representative of every isomorphism class in each exact edge slice. The result was:

[d] Total: 16 cells and 3,887,669 nonisomorphic graphs. In every cell the sole minimizing class was independently recognized as \(K_{d,n-d}\). Combining this exact-slice result with the elementary reduction in Section 2 gives the finite theorem stated at the top.

Why the checker is exact

[d] Enumeration. /usr/bin/nauty-geng generates every unlabeled simple graph of the prescribed order and exact edge count once. No connectivity, bipartiteness, or minimum-degree filter was imposed. The script counts every graph6 record and checks it against a fixed per-cell count.

[a: algorithm correctness; d: execution] Graph6 parsing. The checker decodes graph6 itself and verifies both the vertex count and twice-the-edge-count from the resulting adjacency bitmasks.

[a: algorithm correctness; d: execution] Cycle search. For each starting vertex \(s\), the DFS permits only other path vertices larger than \(s\). Every simple cycle is therefore encountered when \(s\) is its unique least-labelled vertex, and closing a simple path back to \(s\) records its length. All scores are fractions.Fraction values.

[a] Safe pruning. The candidate \(B_d\) is an a priori upper bound. As soon as already witnessed cycle lengths have reciprocal sum strictly greater than the current record, the graph cannot tie or beat it, because finding more cycle lengths only increases the score. A graph at equality is never pruned.

[d] Independent checks. A separate Held–Karp subset/path dynamic program recomputes the cycle-length set for every graph through \(n=8\), every new record, every final minimizer, and each explicitly constructed \(K_{d,n-d}\). The final minimizer is also checked by a separate complete-bipartite recognizer, not by comparing its canonical graph6 string.

[d] Reproducibility. Run:

python runs/erdos65_wave7d_reverify.py --max-n 10

The run used Python 3.12.3 and Nauty/Traces 2.8081 (Debian package nauty 2.8.8+ds-5). The final clean run took 1:46.84 elapsed / 109.08 user CPU seconds and 20,656 KiB maximum RSS. The script prints a SHA-256 digest of each raw graph6 stream so a rerun can compare the exact enumerated inputs.

4. What remains, exactly

[a] Quantifier gap. The computation proves only \(n\le10\). Montgomery's announcement covers \(d\ge d_0\), but supplies neither a public proof nor an explicit \(d_0\). Even if that forthcoming theorem is accepted as stated, the remaining task is still:

with equality only for \(K_{d,n-d}\). The phrase “every \(n\)” is the uniformity step that the finite table does not supply.

[c] Missing structural lemma. A usable bridge would be a finite-kernel/stability lemma: for each fixed \(d\), either prove the inequality directly for all \(n\), or prove that any counterexample has order at most an explicit computable \(N(d)\). Edge deletion alone does not bound \(n\), and ordinary symmetrization is not known to be monotone for the set of cycle lengths. The asymptotic \((1/2-o(1))\log q\) theorem also has no exact error or equality stability strong enough for fixed small \(d\).

[d + c] Computation wall. A count-only Nauty run for the next four exact slices at \(n=11\) found respectively 4,609,179; 70,065,437; 106,321,628; and 86,318,670 isomorphism classes, totaling 267,314,914. Generation alone took 86.02 user CPU seconds. Extrapolating the verified Python cycle-analysis rate, a full \(n=11\) check would cost roughly 2–4 single-core hours, so it was not run on this box. More importantly, any fixed order extension still leaves the uniform all-\(n\) gap.

PARTIAL: Exhaustively verified the exact complete-bipartite minimum and uniqueness for every \(4\le n\le10\) and \(2\le d\le\lfloor n/2\rfloor\); the unresolved step is a uniform fixed-small-\(d\), all-\(n\) structural theorem (or finite-kernel bound).