Problem Statement
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?
Can $G$ be made into a triangle-free graph with diameter $2$ by adding at most $\delta n^2$ edges?
Categories:
Graph Theory
Progress
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.
See also [618].
Source: erdosproblems.com/134 | Last verified: January 13, 2026