OPEN
This is open, and cannot be resolved with a finite computation.
Let $G$ be a connected graph with $n$ vertices, minimum degree $d$, and diameter $D$. Show if that $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ then\[D\leq \frac{2(r-1)(3r+2)}{2r^2-1}\frac{n}{d}+O(1),\]and if $G$ contains no $K_{2r+1}$ and $3r-1 \mid d$ then\[D\leq \frac{3r-1}{r}\frac{n}{d}+O(1).\]
A problem of Erdős, Pach, Pollack, and Tuza
[EPPT89], who gave constructions showing that the above bounds would be sharp, and proved the case $2r+1=3$. It is known (see
[EPPT89] for example) that any connected graph on $n$ vertices with minimum degree $d$ has diameter\[D\leq 3\frac{n}{d+1}+O(1).\]This was disproven for the case of $K_{2r}$-free graphs with $r\geq 2$ by Czabarka, Singgih, and Székely
[CSS21], who constructed arbitrarily large connected graphs on $n$ vertices which contain no $K_{2r}$ and have minimum degree $d$, and diameter\[\frac{6r-5}{(2r-1)d+2r-3}n+O(1),\]which contradicts the above conjecture for each fixed $r$ as $d\to \infty$.
They suggest the amended conjecture, which no longer divides into two cases, that if $G$ is a connected graph on $n$ vertices with minimum degree $d$ which contains no $K_{k+1}$ then the diameter of $G$ is at most\[(3-\tfrac{2}{k})\frac{n}{d}+O(1).\]This bound is known under the weaker assumption that $G$ is $k$-colourable when $k=3$ and $k=4$, shown by Czabarka, Dankelmann, and Székely
[CDS09] and Czabarka, Smith, and Székely
[CSS23].
Cambie and Jooken
[CaJo25] have given an example that shows the diameter for $K_4$-free graphs with minimum degree $16$ is at least $\frac{31}{216}n+O(1)$, giving another counterexample to the original conjecture.
See also
the entry in the graphs problem collection.
View the LaTeX source
View history
Additional thanks to: Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #612, https://www.erdosproblems.com/612, accessed 2026-04-11
