Problem Statement
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)$?
Categories:
Graph Theory
Progress
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].
Source: erdosproblems.com/618 | Last verified: January 15, 2026