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](https://www.erdosproblems.com/65) and its [discussion

thread](https://www.erdosproblems.com/forum/discuss/65) 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

> \[ > \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.

2. Liu–Montgomery proved the asymptotically sharp

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

3. 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.

2. 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.

3. 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](https://rhmontgomery.warwick.ac.uk/papers.html), 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:

| \(n\) | \(d\) | \(d(n-d)\) | isomorphism classes | exact minimum | minimizer count | graph6 witness |

|---:|---:|---:|---:|---:|---:|:---|

| 4 | 2 | 4 | 2 | \(1/4\) | 1 | C] |

| 5 | 2 | 6 | 6 | \(1/4\) | 1 | DFw |

| 6 | 2 | 8 | 24 | \(1/4\) | 1 | E?~o |

| 6 | 3 | 9 | 21 | \(5/12\) | 1 | EFz_ |

| 7 | 2 | 10 | 148 | \(1/4\) | 1 | F?B~o |

| 7 | 3 | 12 | 131 | \(5/12\) | 1 | F?~v_ |

| 8 | 2 | 12 | 1,312 | \(1/4\) | 1 | G??F~w |

| 8 | 3 | 15 | 1,557 | \(5/12\) | 1 | G?B~vo |

| 8 | 4 | 16 | 1,312 | \(13/24\) | 1 | G?~vf_ |

| 9 | 2 | 14 | 15,615 | \(1/4\) | 1 | H???F~} |

| 9 | 3 | 18 | 34,040 | \(5/12\) | 1 | H??F~z{ |

| 9 | 4 | 20 | 27,987 | \(13/24\) | 1 | H?B~vrw |

| 10 | 2 | 16 | 241,577 | \(1/4\) | 1 | I????B~~o |

| 10 | 3 | 21 | 1,251,389 | \(5/12\) | 1 | I???F~}~_ |

| 10 | 4 | 24 | 1,251,389 | \(13/24\) | 1 | I??F~z{~? |

| 10 | 5 | 25 | 1,061,159 | \(77/120\) | 1 | I?B~vrw}? |

[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: