Problem 612

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).

Second statement

Two questions, as the site's commentary reads the display. Let $G$ be a connected graph with $n$ vertices, minimum degree $d$ , and diameter $D$ . (i) If $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ , is $D\leq \frac{2(r-1)(3r+2)}{2r^2-1}\frac{n}{d}+O(1)$ ? (ii) If $G$ contains no $K_{2r+1}$ and $3r-1\mid d$ , is $D\leq \frac{3r-1}{r}\frac{n}{d}+O(1)$ ? Each part is asked for every $r\geq 1$ (part (i) is empty at $r=1$ ), with $O(1)$ allowed to depend on $r$ and $d$ ; the problem is settled when both parts are.

Source: erdosproblems.com/612

Graph theory

Wiki page

Status

ClaimedDisproved

A full solution has been claimed but not yet accepted. The statement is false.

The site labels the problem OPEN. Read as the two questions of the Statement (precise), part (i) is disproved and part (ii) is open. Part (i) is false: for every $r\ge2$ and every $\delta>2(r-1)(3r+2)(2r-3)$ with $(r-1)(3r+2)\mid\delta$ by Theorem 6 of the arXiv preprint of Czabarka, Singgih and Székely (its Section 3, published as J. Combin. Theory Ser. B 151 (2021), 38--45, refereed; the published numbering is unchecked), the accepted claim page of Czabarka, Singgih and Székely, and at $r=2$ , $\delta=16$ by the claimed page of Cambie and Jooken (2025 preprint). Part (ii) is proved for $r=1$ by Theorem 2 of Erdős, Pach, Pollack and Tuza (the accepted partial claim page Erdős, Pach, Pollack and Tuza, refereed) and undecided for $r\ge2$ in the refereed sources cited here; September 2026 forum posts report a preprint refuting it for every $r\ge4$ and Lean-checked, AI-assisted arguments that it holds for $r=2$ and fails for $r=3$ , recorded on the claimed pages of Chen and Chen (part (ii) for every $r\ge4$ and every large $\delta$ divisible by $3r-1$ , preprint) and Kitamura (part (ii) refuted at $r=3$ , $\delta=800$ , for every additive constant, and proved at $r=2$ ; Lean files). The frontmatter standing is derived from the claim pages: part (i) is settled by the accepted refutation, and part (ii) only by these pending refutations, so the problem is claimed, disproved. This standing departs from the site's OPEN only by counting those pending refutations, which no outside review has accepted; it agrees with the label that no accepted claim settles part (ii), and it becomes solved, disproved if either refutation of part (ii) is accepted.

Notes

The site's wording displays two bounds under one 'Show if that', the Conjecture of Erdős, Pach, Pollack and Tuza (1989, pp. 78--79), stated there for natural numbers $r,\delta>1$ . Read as one statement, it is a conjunction over all $r$ and all admissible $d$ , and it is false: Theorem 6 of Czabarka, Singgih and Székely (J. Combin. Theory Ser. B 151 (2021), refereed) gives, for every $r\geq 2$ and every large $d$ divisible by $(r-1)(3r+2)$ , connected $K_{2r}$ -free graphs of diameter $\frac{6r-5}{(2r-1)d+2r-3}n+O(1)$ , above the first bound; Cambie and Jooken (2025 preprint) add $r=2$ , $d=16$ . The site cites both results in its commentary, calls the first a disproof 'for the case of $K_{2r}$ -free graphs', and keeps the label OPEN while presenting the amended conjecture of Czabarka, Singgih and Székely as the live question. The page follows that reading: the display is two questions, part (i) for $K_{2r}$ -free and part (ii) for $K_{2r+1}$ -free graphs, and the problem is settled only when both are. Under the site's wording, read as one conjunction, the problem is disproved; under the site's reading part (i) is disproved and part (ii) is open, proved at $r=1$ by Theorem 2 of the 1989 paper, with unreviewed claims that it holds at $r=2$ and fails at $r=3$ (Kitamura's Lean files, not built here) and fails for every $r\geq 4$ (Chen and Chen's preprint, cited from its abstract). If any of those refutations is accepted, part (ii) and so the whole problem is disproved under both readings. The curator has not stated this reading in the thread; it is inferred from the label and the commentary.

EPPT89: Erdős, Paul and Pach, János and Pollack, Richard and Tuza, Zsolt, Radius, diameter, and minimum degree. J. Combin. Theory Ser. B 47 (1989), no. 1, 73--79; doi:10.1016/0095-8956(89)90066-X. Theorem 1, p. 73; Theorem 2, p. 76; Theorem 3, p. 77; Conjecture, pp. 78--79. Library home: Erdős et al. 1989.
CSS21: Czabarka, Éva and Singgih, Inne and Székely, László A., Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza. J. Combin. Theory Ser. B 151 (2021), 38--45; doi:10.1016/j.jctb.2021.06.001. The library folder Czabarka 2021 carries this citation and covers arXiv:2009.02611v1 (5 September 2020, 23 pages), titled "On the maximum diameter of $k$ -colorable graphs", and the published article of that title, Electron. J. Combin. 28 (2021), no. 3, P3.52 (doi:10.37236/10382; open access). The preprint's parts went to the two papers: its Section 3 counterexample (Theorem 6, pp. 7--8) is the JCTB paper, which the EJC article's reference [4] (p. 20) cites as "J. Combin. Theory B 151 (2021), 38--45" in place of reproducing it, and its $k$ -colorable results are the EJC article (preprint Theorems 3, 4 and 11 and Conjecture 2 are EJC Theorems 5, 6 and 12 and Conjecture 4; the label Theorem 6 names the counterexample only in the preprint). Locators below are to the preprint. The JCTB article is not held; the EJC reference confirms its volume and pages, and its DOI and theorem numbering are unchecked. The reference lists of the preprint and the EJC article cite [EPPT89] with the pages 279--285; the article's pages are 73--79.
CSS23: Czabarka, Éva and Smith, Stephen J. and Székely, László, Maximum diameter of 3- and 4-colorable graphs. J. Graph Theory 102 (2023), no. 2, 262--270; doi:10.1002/jgt.22869 (online 3 August 2022). Theorem 4, p. 2 of arXiv:2109.13887v1 (28 September 2021). Library home: Czabarka, Smith and Székely 2023.
CDS09: Czabarka, É. and Dankelmann, P. and Székely, L. A., Diameter of 4-colourable graphs. European J. Combin. 30 (2009), no. 5, 1082--1089; doi:10.1016/j.ejc.2008.09.005 (available online 30 September 2008). Conjecture 1 and the $r=2$ construction, pp. 1082--1083; Theorem 1, p. 1083. Library home: Czabarka and Székely 2009. Its theorem is quoted as Theorem 2 on p. 2 of [CSS21] and of [CSS23].
CaJo25: S. Cambie and J. Jooken, Sharp results for the Erdős, Pach, Pollack and Tuza problem. arXiv:2502.08626v1 (12 February 2025), 16 pp.; preprint, no later version and no journal record found on 2026-09-17. Table 1 and the following paragraph, p. 4; the $\delta=16$ block, p. 11. Library home: Cambie 2025.
ChCh26: Chen, Hangdi and Chen, Yaojun, Counterexamples to two conjectures on the diameter of clique-free graphs. arXiv:2609.03346v1 (3 September 2026); preprint, not held; cited from its arXiv abstract. Lead from the discussion thread.

Problem 612

Second statement

Status

Notes

Proof claims

Discussion