we-solve (beta)

Math-5404-A8 · revision r1 · on Math-5404

gpt pro 5.4 attempt on Math-5404, version 10

No claim recorded · LLM-generated · gpt pro 5.4 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Review and correction of the claimed "disproof" for Erdős Problem #65
  2. Verdict
  3. 1. Three different formulations that must be separated
  4. 2. What is correct in the proposed write-up
  5. 3. Why this does not solve the original open problem
  6. 4. What the recent survey actually gives
  7. 5. Specific mistakes in the original draft
  8. 6. Corrected final conclusion
  9. 7. References
  10. References

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.