Diameter of a \(K_r\)-free graph

A problem on the diameter of a \(K_r\)-free graph (proposed by Erdös, Pach, Pollack and Tuza [1])

Let \(G\) denote a connected graph on \(n\) vertices with minimum degree \(\delta\). Show that if \(G\) is \(K_{2r}\)-free and \(\delta\) is a multiple of \((r-1)(3r+2)\), then the diameter of \(G\), denoted by \(D(G)\), satisfies \[ D(G) \leq \frac{2(r-1)(3r+2)}{(2r^2-1)\delta}n +O(1) \] as \(n\) approaches infinity. If \(G\) is \(K_{2r+1}\)-free and \(\delta\) is a multiple of \(3r-1\), then show that \[ D(G) \leq \frac{3r-1}{r\delta}n + O(1) \] as \(n\) approaches infinity.

In [1], bounds for the diameters of triangle-free or \( C_k\)-free graphs with given minimum degree were derived.


Bibliography
1 P. Erdös, J. Pach, R. Pollack and Zs. Tuza, Radius, diameter, and minimum degree, J. Comb. Theory Ser. B 47 (1989), 73-79.