Problem Statement
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).\]
Categories:
Graph Theory
Progress
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.
Source: erdosproblems.com/612 | Last verified: January 15, 2026