Erdős Problem #65

Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 13

1) ROUND-13 OBJECTIVE

Path chosen: (A) proof-oriented gap closure on the original 1981 conjecture. After the correction in the user's review, the relevant statement is Erdős's 1981 strengthened conjecture: for integers $n\ge 2k$, among all graphs on $n$ vertices and exactly $k(n-k)$ edges, is \[ S(G):=\sum_{\ell\in \mathcal C(G)}\frac1\ell \] minimised by the complete bipartite graph $K_{k,n-k}$?

In this round I do not claim a full proof. Instead I prove a new and quite strong reduction:

assuming the large-$d$ threshold theorem quoted in Montgomery's 2025 survey, the original 1981 conjecture is already true for every $n\ge 2d_0$, where $d_0$ is the threshold from that theorem. Consequently, only finitely many exact parameter pairs $(n,k)$ remain open.

This is the most promising next step because it works with the actual conjecture, not an over-broad reformulation, and it converts the survey's threshold statement into a finite reduction of the original exact-edge problem.

2) Round-12 FOUNDATION USED

I use the following vetted facts.

• $F1$ For integers $a,b\ge 1$, the complete bipartite graph $K_{a,b}$ has \[ \mathcal C(K_{a,b})=\{4,6,\dots,2\min\{a,b\}\}, \qquad S(K_{a,b})=\frac12\left(H_{\min\{a,b\}}-1\right). \] In particular, \[ S(K_{k,n-k})=\frac12(H_k-1)=\frac12\left(\frac12+\frac13+\cdots+\frac1k\right) \qquad (n\ge 2k). \]

• $F2$ Round 10 proved the exact $k=2$ line through $n=51$: \[ \min\{S(G): |V(G)|=n,\ |E(G)|=2n-4\}=\frac14 \qquad (7\le n\le 51), \] attained by $K_{2,n-2}$.

• $F3$ Montgomery's 2025 survey states the following forthcoming theorem: there exists an integer $d_0$ such that for every integer $d\ge d_0$, among the $n$-vertex graphs with at least $d(n-d)$ edges, the quantity $S(G)$ is minimised exactly by the graph $K_{d,n-d}$.

3) NEW INSIGHT / TOOL (ROUND-13)

The new observation is a symmetry reduction which was not exploited in the earlier rounds.

The original 1981 conjecture is parameterised by the smaller part $k$ (since $n\ge 2k$), but Montgomery's threshold theorem is stated for an arbitrary parameter $d$ in the edge count $d(n-d)$. Since \[ k(n-k)=(n-k)k, \] one can apply the survey theorem with \[ d:=n-k, \] that is, with the larger part size.

Because $n\ge 2k$, we have $n-k\ge n/2$. Therefore whenever $n\ge 2d_0$ one gets \[ d=n-k\ge d_0, \] and the survey theorem applies automatically.

So the original conjecture is already settled for all sufficiently large $n$; only finitely many small values of $n$ remain.

4) ATTACK PLAN (ROUND-13)

The exact gap after Round 12 is the actual 1981 conjecture: \[ \text{for }n\ge 2k,\quad \min\{S(G): |V(G)|=n,\ |E(G)|=k(n-k)\}=S(K_{k,n-k})\ ? \]

The Round 13 plan is:

1. restate Erdős's 1981 conjecture in its original exact-edge form;
2. derive an exact-edge corollary from the survey's threshold theorem;
3. apply that corollary with $d=n-k$ rather than $d=k$;
4. conclude that every case with $n\ge 2d_0$ is solved, leaving only finitely many pairs $(n,k)$ with $n<2d_0$.

5) WORK (ROUND-13)

As before, for a graph $G$ let \[ \mathcal C(G):=\{\ell\ge 3 : \text{$G$ contains a cycle of length $\ell$}\}, \qquad S(G):=\sum_{\ell\in\mathcal C(G)}\frac1\ell. \]

5.1. Erdős's original 1981 strengthened conjecture

The relevant exact-edge statement from Erdős 1981 is:

For $n\ge 2k$, every graph $G(n; k(n-k))$ should satisfy \[ S(G)\ge \frac12\left(\frac12+\frac13+\cdots+\frac1k\right), \] and equality should be attained by the complete bipartite graph with parts of sizes $k$ and $n-k$.

By $F1$, this lower bound is exactly $S(K_{k,n-k})$.

5.2. Exact-edge corollary of the survey theorem

Lemma 5.1. Assume $F3$. Then for every integer $d\ge d_0$ and every integer $n\ge d$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=d(n-d)\}=S(K_{d,n-d}), \] and the minimiser is unique, namely $K_{d,n-d}$.

Proof. The exact-edge class \[ \{G: |V(G)|=n,\ |E(G)|=d(n-d)\} \] is a subclass of the threshold class \[ \{G: |V(G)|=n,\ |E(G)|\ge d(n-d)\}. \] By $F3$, the minimum of $S(G)$ on the larger class is attained exactly by $K_{d,n-d}$. Therefore the same is true on the smaller exact-edge class. $\square$

5.3. All sufficiently large $n$ are solved

Theorem 5.2. Assume $F3$. Let $n,k$ be integers with \[ n\ge 2k \qquad\text{and}\qquad n\ge 2d_0. \] Then among all $n$-vertex graphs with exactly $k(n-k)$ edges, \[ S(G)\ge S(K_{k,n-k})=\frac12(H_k-1), \] with equality if and only if $G\cong K_{k,n-k}$.

Proof. Fix such $n,k$, and set \[ d:=n-k. \] Since $n\ge 2k$, we have \[ d=n-k\ge n/2\ge d_0. \] Also \[ d(n-d)=(n-k)k=k(n-k). \] Therefore Lemma 5.1 applies with this value of $d$, and gives \[ \min\{S(G): |V(G)|=n,\ |E(G)|=k(n-k)\}=S(K_{d,n-d}). \] But \[ K_{d,n-d}=K_{n-k,k}\cong K_{k,n-k}, \] so the claimed conclusion follows. $\square$

5.4. Finite reduction of the original conjecture

Corollary 5.3. Assume $F3$. Then Erdős's 1981 strengthened conjecture is equivalent to the finite set of cases \[ 1\le k\le n/2 \qquad\text{and}\qquad n<2d_0. \] Equivalently, only finitely many parameter pairs $(n,k)$ remain unresolved.

Proof. By Theorem 5.2, every case with $n\ge 2d_0$ is already true. Hence only cases with $n<2d_0$ remain. For each such $n$, the constraint $n\ge 2k$ means $1\le k\le \lfloor n/2\rfloor$, so there are only finitely many pairs $(n,k)$. Conversely, if those finitely many remaining pairs are verified, then the theorem is proved for all $(n,k)$. $\square$

5.5. Interaction with the earlier $k=2$ line

Remark 5.4. Round 10 already proved the exact $k=2$ line for all $7\le n\le 51$. Combined with Corollary 5.3, this means:

• the original 1981 conjecture is proved for all $k=2$ with $7\le n\le 51$ by direct argument;
• it is proved for every $(n,k)$ with $n\ge 2d_0$ by Theorem 5.2;
• therefore the only unresolved part of the original conjecture is a finite set of small parameter pairs, all lying in the box $n<2d_0$.

This is a strict improvement over the Round 11 status picture, which still described the unsolved regime as if it were an infinite family in $n$.

6) ADVERSARIAL VERIFICATION

• Original formulation versus over-broad reformulation. Theorem 5.2 applies to Erdős's actual 1981 exact-edge conjecture, namely the case $|E(G)|=k(n-k)$ with $n\ge 2k$. It does not use the over-broad "all exact pairs $(n,m)$" formulation that the user correctly rejected.

• Legitimacy of using $d=n-k$. The survey theorem is stated for every integer $d\ge d_0$ in the edge count $d(n-d)$. Since \[ k(n-k)=(n-k)k, \] there is no obstruction to applying it with the larger part size $d=n-k$.

• Threshold to exact-edge passage. Lemma 5.1 is logically valid because the exact-edge class is contained in the threshold class and contains the candidate minimiser itself.

• Finiteness claim. Corollary 5.3 leaves only pairs with $n<2d_0$ and $1\le k\le n/2$. This set is finite regardless of the (possibly unknown) size of $d_0$.

• What is still missing. The argument does not give an explicit value of $d_0$, and therefore does not by itself yield a fully explicit finite list of remaining cases. That is the genuine remaining gap.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The corrected original 1981 conjecture is not disproved. But Round 13 proves a substantial new reduction: assuming the large-$d$ threshold theorem stated in Montgomery's 2025 survey, the original exact-edge conjecture is already true for every \[ n\ge 2d_0, \] and hence only finitely many parameter pairs $(n,k)$ remain open. So the conjecture has now been reduced from an infinite family of cases to a finite one.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 93%

9) REFERENCES

References

• [Erdos1981] P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 $1981$, 25--42. Used here for the original exact-edge formulation on graphs $G(n; k(n-k))$.
• [Montgomery2025] R. Montgomery, Cycles and expansion in graphs, EMS Magazine 138 $2025$, 5--12. Used here for the quoted forthcoming theorem that there exists $d_0$ such that for every $d\ge d_0$, among $n$-vertex graphs with at least $d(n-d)$ edges, $S(G)$ is minimised exactly by $K_{d,n-d}$.

Review and correction of the claimed "disproof" for Erdős Problem #65

Verdict

The arithmetic observation in the proposed write-up is correct, but it does not solve Erdős Problem #65 as stated in the original source. It only disproves an over-generalised reformulation that asks for a complete bipartite minimiser for every exact pair $(n,m)$. The original 1981 strengthening of Erdős is narrower: it asks about graphs with exactly $k(n-k)$ edges, i.e. precisely the edge counts realised by $K_{k,n-k}$.

Accordingly, the claims

"FULL SOLUTION --- COUNTEREXAMPLE / DISPROOF"   and   "COMPLETION: 100%"

are incorrect for the original open problem.

1. Three different formulations that must be separated

The literature contains three related but distinct questions.

1. (A) The 1975 exact-edge minimisation problem. Erdős wrote: for graphs $G(n;\lfloor kn\rfloor)$, determine or estimate the minimum of \[ \sum_{r\in \mathcal C(G)} \frac1r. \] He said it seemed likely that this minimum is $(\tfrac12+o(1))\log k$.

2. (B) The 1981 strengthened conjecture. Erdős then proposed a sharper statement: if $n\ge 2k$, then for every graph $G(n;k(n-k))$, \[ \sum_{u_i\in \mathcal C(G)} \frac1{u_i} \ge \frac12\left(\frac12+\frac13+\cdots+\frac1k\right), \] and in his own words this means the sum is minimum for the complete bipartite graph with parts of sizes $k$ and $n-k$.

3. (C) The over-generalised exact-$(n,m)$ reformulation. For every fixed exact pair $(n,m)$, minimise $S(G)$ over all $n$-vertex $m$-edge graphs and ask whether the minimiser is complete bipartite.

The proposed write-up correctly disproves (C), but the original conjectural minimiser statement in Erdős 1981 is (B), not (C).

2. What is correct in the proposed write-up

The following observation is valid.

Proposition 2.1. Let $n=2t+1$ with $t\ge 2$. A complete bipartite graph on $n$ vertices has exactly $a(n-a)$ edges for some integer $a$, so the possible edge counts are \[ a(2t+1-a)\qquad(0\le a\le 2t+1). \] The largest such value is $t(t+1)$, attained at $a=t,t+1$, and the next largest is \[ (t-1)(t+2)=t(t+1)-2. \] Hence there is no complete bipartite graph on $2t+1$ vertices with exactly \[ m=t(t+1)-1 \] edges.

Therefore, if one asks the universal exact-edge question (C), then that question is false: the class of graphs with $(n,m)=(2t+1,t(t+1)-1)$ is nonempty and finite, so a minimiser of $S(G)$ exists, but no complete bipartite graph lies in that class.

3. Why this does not solve the original open problem

The counterexample above does not apply to Erdős's 1981 strengthening, because that conjecture only concerns edge counts of the form \[ m=k(n-k), \] exactly the counts realised by the candidate extremal graph $K_{k,n-k}$.

So the right conclusion is:

The proposed argument refutes only the over-broad formulation (C). It does not refute, and does not settle, the original conjecture (B).

In particular, the sentence

"The minimal corrected exact-edge question is then: whenever $m=a(n-a)$, is the minimum attained by $K_{a,n-a}$?"

is not a new correction at all: it is essentially Erdős's original 1981 strengthened conjecture.

4. What the recent survey actually gives

Montgomery's 2025 survey states that in forthcoming work with Milojević, Pokrovskiy, and Sudakov, there is a threshold $d_0$ such that for every $d\ge d_0$, among all $n$-vertex graphs with at least $d(n-d)$ edges, \[ \sum_{\ell\in \mathcal C(G)} \frac1\ell \] is minimised exactly by the complete bipartite graph $K_{d,n-d}$.

This is a threshold theorem, but it also immediately implies the corresponding exact-edge statement for the special edge count $m=d(n-d)$: since $K_{d,n-d}$ belongs to the class of graphs with exactly $d(n-d)$ edges, uniqueness in the larger "at least" class forces it also to be the minimiser in the exact class.

Thus the survey gives genuine partial progress on the original 1981 conjecture, for all sufficiently large $d$.

5. Specific mistakes in the original draft

1. The phrase "under the exact-edge interpretation of Problem 65" is misleading. The original 1981 source does not formulate the complete-bipartite conjecture for arbitrary exact pairs $(n,m)$.

2. Theorem 5.3 is mathematically correct only as a disproof of the over-generalised formulation (C), not of Erdős Problem 65 in its original strengthened form.

3. The sentence calling the "corrected exact-edge question" the version with $m=a(n-a)$ is historically inaccurate: that is already the original 1981 conjecture.

4. The note says the large-$d$ survey theorem only addresses a threshold formulation. That is incomplete. It also yields the exact-edge statement for $m=d(n-d)$.

5. The final verdict "FULL SOLUTION --- COUNTEREXAMPLE / DISPROOF" is false as a verdict on the original open problem.

6. The completion estimate "100%" is false for the original problem.

7. The bibliographic reference "EMS Magazine 138 (2025/2026 issue)" should be corrected to EMS Magazine 138 $2025$.

8. If one keeps a statement ranging over $0\le a\le n$, then degenerate cases $a=0,n$ should be separated from formulas involving harmonic numbers. For cycle questions, the natural nontrivial range is $1\le a\le n-1$.

6. Corrected final conclusion

Correct conclusion. The proposed note does not provide a satisfactory solution to Erdős Problem #65. What it does show is the following:

If one over-generalises the minimiser question to arbitrary exact edge classes $(n,m)$, then that over-generalised statement is trivially false because many edge counts are not realised by any complete bipartite graph on $n$ vertices.

This is a valid clarification, but it is not a solution of the original conjecture, which already restricts to the exact edge count $m=k(n-k)$.

The best current picture from the checked sources is therefore:

• the broad lower-bound problem was introduced earlier and has asymptotically sharp lower bounds;
• Erdős's 1981 complete-bipartite strengthening remains open in general;
• Montgomery's 2025 survey reports a forthcoming exact extremal theorem proving the conjectured complete-bipartite minimiser for all sufficiently large $d$, in the class of graphs with at least $d(n-d)$ edges, and hence also for the exact edge count $d(n-d)$.

7. References

References

• [Erdos1975] P. Erdős, Problems and results on finite and infinite graphs, available at the Rényi archive $1975$.
• [Erdos1981] P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 $1981$, 25--42.
• [GPVS1985] A. Gyárfás, H. J. Prömel, B. Voigt, and E. Szemerédi, On the sum of the reciprocals of cycle lengths in sparse graphs, Combinatorica 5 $1985$, 41--52.
• [Montgomery2025] R. Montgomery, Cycles and expansion in graphs, EMS Magazine 138 $2025$, 5--12.
• [Problem65Page] T. F. Bloom, Erdős Problem #65, online problem page, accessed 2026-03-09.

Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 5

1) ROUND-5 OBJECTIVE

Path chosen: (A) proof-oriented gap closure. Round 4 proved the complete-bipartite minimiser statement on the line \[ |E(G)|=2|V(G)|-4 \] up to $n=13$, with the first unresolved point isolated at $n=14$. In this round I use exact small-order extremal data for forbidden cycle families to push the same line much further. The new goal is:

prove that for every $7\le n\le 23$, among all $n$-vertex graphs with $2n-4$ edges, the minimum of \[ S(G)=\sum_{\ell\in\mathcal C(G)}\frac1\ell \] is $1/4$, attained by $K_{2,n-2}$.

This is the most promising direction because Round 4 had already reduced the problem to controlling graphs with no short cycles, and exact extremal numbers for the forbidden families $\{C_3,C_4,C_5\}$ and $\{C_3,C_4,C_6\}$ are available in the relevant range.

2) Round-4 FOUNDATION USED

I rely on the following vetted Round 4 results as black boxes.

• $F1$ For $2\le a\le b$, the complete bipartite graph $K_{a,b}$ has \[ \mathcal C(K_{a,b})=\{4,6,\dots,2a\}, \qquad S(K_{a,b})=\sum_{j=2}^a\frac1{2j}=\frac12(H_a-1). \] In particular, \[ S(K_{2,n-2})=\frac14. \]

• $F2$ Round 3 proved that for every $7\le n\le 12$ and $m=2n-4$, every $n$-vertex $m$-edge graph satisfies $S(G)\ge 1/4$, with equality attained by $K_{2,n-2}$.

• $F3$ Round 4 proved the next case $(n,m)=(13,22)$: every $13$-vertex $22$-edge graph satisfies $S(G)\ge 1/4$, with equality attained by $K_{2,11}$.

Thus Round 4 already settled the line $m=2n-4$ for all $7\le n\le 13$.

3) NEW INSIGHT / TOOL (ROUND-5)

The new ingredient is the use of exact extremal numbers for small forbidden cycle families. Write \[ \operatorname{ex}(n;\mathcal F) \] for the maximum number of edges in an $n$-vertex graph containing no member of $\mathcal F$. The ANU extremal-graph tables provide the exact values of \[ \operatorname{ex}(n;\{C_3,C_4,C_5\}) \qquad\text{and}\qquad \operatorname{ex}(n;\{C_3,C_4,C_6\}) \] for all $n$ in the range relevant here.

These data give a new uniform mechanism:

• if $G$ has $2n-4$ edges and no $C_3,C_4$, then comparison with $\operatorname{ex}(n;\{C_3,C_4,C_5\})$ forces a $C_5$ whenever $2n-4$ exceeds that extremal value;
• similarly, comparison with $\operatorname{ex}(n;\{C_3,C_4,C_6\})$ forces a $C_6$.

This simultaneously settles $14\le n\le 22$. For $n=23$, where $\operatorname{ex}(23;\{C_3,C_4,C_5\})=42$ is exactly the target edge count, the same data identify a unique exceptional graph with no $C_3,C_4,C_5$; an explicit verification on that graph then finishes the case.

4) ATTACK PLAN (ROUND-5)

The exact gap left by Round 4 was the unresolved tail of the $K_{2,n-2}$ line beyond $n=13$.

The plan is:

1. Use $F2$--$F3$ to reduce to $14\le n\le 23$.
2. For $14\le n\le 22$, show that any graph with $2n-4$ edges must contain either $C_3$ or $C_4$, or else both $C_5$ and $C_6$.
3. Handle $n=23$ separately:
   • if a $23$-vertex $42$-edge graph has a $C_5$, then together with a forced $C_6$ we are done;
   • if it has no $C_5$, exact extremal data force it to be the unique published girth-$6$ extremal graph on $23$ vertices and $42$ edges, and that explicit graph contains both a $6$-cycle and an $8$-cycle.
4. Compare against $K_{2,n-2}$, which always gives $S=1/4$.

This not only extends the solved range but also isolates a new sharp obstruction: $n=24$ is the first point on the line $m=2n-4$ where the exact value \[ \operatorname{ex}(24;\{C_3,C_4,C_5\})=45 \] exceeds the target edge count $44$, so the present forcing strategy no longer compels a $5$-cycle.

5) WORK (ROUND-5)

As before, for a graph $G$ let \[ \mathcal C(G):=\{\ell\ge 3:\text{$G$ contains a cycle of length $\ell$}\}, \qquad S(G):=\sum_{\ell\in\mathcal C(G)}\frac1\ell. \]

5.1. Exact small-order extremal values

From the exact extremal tables checked in Round 5, we use the following values. Set \[ a_n:=\operatorname{ex}(n;\{C_3,C_4,C_5\}), \qquad b_n:=\operatorname{ex}(n;\{C_3,C_4,C_6\}). \] Then for $14\le n\le 23$ one has \[ \begin{array}{c|cccccccccc} n & 14&15&16&17&18&19&20&21&22&23\\\hline a_n & 21&22&24&26&29&31&34&36&39&42\\ b_n & 18&20&22&24&27&28&30&32&34&36\\ 2n-4 & 24&26&28&30&32&34&36&38&40&42 \end{array} \] In particular, \begin{equation}\label{wsref-0-65-71-3a-73-74-72-69-63-74-31-34-74-6f-32-32} 2n-4>a_n\quad\text{and}\quad 2n-4>b_n\qquad(14\le n\le 22), \end{equation} and at $n=23$ we have \begin{equation}\label{wsref-0-65-71-3a-6e-32-33-65-78-61-63-74} a_{23}=42, \qquad b_{23}=36<42. \end{equation}

5.2. Uniform extension through $n=22$

5.3. The $n=23$ case

We now settle the first value not covered by Proposition prop:14-22.

5.4. Main Round-5 theorem

6) ADVERSARIAL VERIFICATION

• Use of Round 4 results. I used Round 4 only as foundation for the already solved cases $7\le n\le 13$ and the formula $S(K_{2,n-2})=1/4$. No Round 4 proof was reproved.

• Dependence on external tables. The argument for $14\le n\le 23$ uses only exact table entries (not asymptotics): the ANU page explicitly states that when neither "ne" nor "ng" is preceded by $\ge$, the Turán number and all extremal graphs are exact. That hypothesis holds for every table entry used here.

• Strict inequalities for $14\le n\le 22$. These were checked entry-by-entry in (eq:strict14to22). There is no hidden asymptotic step.

• The $n=23$ boundary case. Here the $C_5$-forcing inequality fails exactly, since $a_{23}=42=2\cdot 23-4$. The proof therefore isolates the no-$C_5$ case and handles it separately via the unique extremal graph $H$. This is the only place where the argument uses an explicit graph.

• Computational content in Lemma lem:23-unique. The computational step is exact and finite: one decodes a published sparse6 graph and reads off the listed edges, which visibly contain one $6$-cycle and one $8$-cycle. No random search or heuristic is used.

• Why equality cannot occur away from $K_{2,n-2}$. Every non-$K_{2,n-2}$ case handled in the proof actually gives a strict inequality $S(G)>1/4$ (either from a triangle, from $C_5$ and $C_6$, or from $C_6$ and $C_8$ in the exceptional $n=23$ graph).

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 5 proves a substantially stronger theorem than Round 4: for every $7\le n\le 23$, among all graphs with $n$ vertices and $2n-4$ edges, \[ \min S(G)=\frac14, \] and the complete bipartite graph $K_{2,n-2}$ is a minimiser. Thus the entire $a=2$ complete-bipartite line is now settled up to $n=23$. The first unresolved value on this line is $n=24$. The full Erdős--Hajnal minimiser question for arbitrary $(n,m)$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 90%

9) REFERENCES

References

• [AfzalyMcKayData] N. Afzaly and B. D. McKay, Extremal Graphs and Turan numbers (combinatorial data page), Australian National University. Used here for the exact tables for $\operatorname{ex}(n;\{C_3,C_4,C_5\})$ and $\operatorname{ex}(n;\{C_3,C_4,C_6\})$.
• [McKay23Graph] B. D. McKay, Sparse6 file for the unique graph on $23$ vertices and $42$ edges with no $C_3,C_4,C_5$, file c345_n23e42.s6 on the ANU extremal-graph data page. Used here only for the exact finite verification in Lemma lem:23-unique.