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\le \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\le \frac{3r-1}{r}\frac{n}{d}+O(1).$$

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

The two displayed inequalities are exactly the **Erdős–Pach–Pollack–Tuza (1989)** conjectures (often listed as Erdős problem #612). ([Homepages UC][1])

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.