Erdős Problem #134

Let \(\epsilon,\delta>0\) and \(n\) be sufficiently large in terms of \(\epsilon\) and \(\delta\). Let \(G\) be a triangle-free graph on \(n\) vertices with maximum degree \(<n^{1/2-\epsilon}\). Can \(G\) be made into a triangle-free graph with diameter \(2\) by adding at most \(\delta n^2\) edges? Asked by Erdős and Gyárfás, who proved that this is the case when \(G\) has maximum degree \(\ll \log n/\log\log n\). A construction of Simonovits shows that this conjecture is false if we just have maximum degree \(\leq Cn^{1/2}\), for some large enough \(C\). In this note Alon solves this problem in a strong form, in particular proving that a triangle-free graph on \(n\) vertices with maximum degree \(<n^{1/2-\epsilon}\) can be made into a triangle-free graph with diameter \(2\) by adding at most \(O(n^{2-\epsilon})\) edges.