Problem Statement
For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$ (while preserving the property of being triangle-free).
Is it true that there exists a constant $c>0$ such that if $G$ is a connected graph on $n$ vertices then $h_4(G)<(1-c)n$?
Is it true that there exists a constant $c>0$ such that if $G$ is a connected graph on $n$ vertices then $h_4(G)<(1-c)n$?
Categories:
Graph Theory
Progress
A problem of Erdős, Gyárfás, and Ruszinkó [EGR98] who proved that $h_3(G)\leq n$ and $h_5(G) \leq \frac{n-1}{2}$ and there exist connected graphs $G$ on $n$ vertices with $h_3(G)\geq n-c$ for some constant $c>0$.If we omit the condition that the graph must remain triangle-free then Alon, Gyárfás, and Ruszinkó [AGR00] have proved that adding $n/2$ edges always suffices to obtain diameter at most $4$.
See also [134] and [618].
Source: erdosproblems.com/619 | Last verified: January 15, 2026