PROVED (LEAN)
This has been solved in the affirmative and the proof verified in Lean.
For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$ and is still triangle-free. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$?
A problem of Erdős, Gyárfás, and Ruszinkó
[EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$.
Erdős, Gyárfás, and Ruszinkó
[EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.
Alon has observed this problem is essentially identical to
[134], and his solution in
this note also solves this problem in the affirmative.
See also
[619].
View the LaTeX source
Additional thanks to: Noga Alon
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #618, https://www.erdosproblems.com/618, accessed 2026-02-13
