Claims

../

1998_01_01_erdos_gyarfas_ruszinko: A triangle-free graph of maximum degree o(n^{1/4}/log n) reaches diameter two with o(n squared) added edges, which answers the problem yes for every epsilon above one quarter.

2024_07_01_alon: Alon's Theorem 3.2 adds at most 2.5 c(n) n squared edges to a triangle-free graph on n vertices of maximum degree at most c(n) root n and reaches diameter two; with c(n) a negative power of n the problem's answer is yes.

---