Problem 934

Let $h_t(d)$ be minimal such that every graph $G$ with $h_t(d)$ edges and maximal degree $\leq d$ contains two edges whose shortest path between them has length $\geq t$ .

Estimate $h_t(d)$ .

Source: erdosproblems.com/934

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. No estimate of $h_t(d)$ up to a factor $1+o(1)$ for general $t$ , and no "nice expression" in Erdős's sense, was found in the search whose scope the Current assessment records. Known exactly: $h_1(d)=d+1$ for $d\ge3$ ; $h_2(d)=\frac54d^2+1$ for even $d$ and $\frac{5d^2-2d+1}4+1$ for odd $d$ (Chung, Gyárfás, Tuza and Trotter 1990, refereed; an accepted partial claim on its claim page (Chung, Gyárfás, Tuza and Trotter, 1990)); $h_3(3)=23$ (Cambie, Cames van Batenburg, de Joannis de Verclos and Kang, SIAM J. Discrete Math. 2022, refereed; an accepted partial claim on its claim page (Cambie Cames Van Batenburg De Joannis De Verclos Kang, 2021)). In general $h_t(d)\le\frac32d^t+1$ for all $t\ge1$ and $h_t(d)\ge0.629^td^t$ for all large $t$ and infinitely many $d$ (the same paper), with $h_t(d)\le d^t+1$ for graphs without a $(2t+1)$ -cycle. Two preprints of 2026 change the picture at $t=3$ and for the asymptotics: Kumar, Mohar and Pragada refute the 2022 conjecture $h_3(d)\le d^3-d^2+d+2$ at $d=4$ ( $h_3(4)\ge71>54$ ) and prove $\liminf h_3(d)/d^3\ge\frac{253}{225}$ (a pending partial claim on its claim page (Kumar, Mohar and Pragada, 2026)), and Korsky claims on the site's proof-claim tab, and Cames van Batenburg and Korsky in a preprint, $h_t(d)\ge(1-o(1))d^t$ as $d\to\infty$ for every $t\ge3$ (the preprint's abstract states it for every $t\ge2$ ), a result first submitted to the tab on 29 July 2026 and recorded as a pending partial claim on its claim page (Korsky, 2026); both are unrefereed and recorded as claimed progress. A thread post and Zenodo manuscript of 17 August 2026 claim the exact value $h_3(4)=71$ with a Lean 4 development, a pending partial claim on its claim page (BitterLemma, 2026). This is a bounded negative finding, not a certificate of openness.

Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 1, printed p. 81. Library home: Erdős 1988.
BBPP83: Bermond, J.-C., Bond, J., Paoli, M. and Peyrat, C., Graphs and interconnection networks: diameter and vulnerability. Surveys in Combinatorics 1983 (Proc. Ninth British Combinatorial Conference), London Math. Soc. Lecture Note Ser. 82 (1983), 1--30 (the venue from the citing papers; the site's text prints "(1983), 1-30"). The HAL deposit is a two-up scan of the typescript without page numbers; in it the passage is on PDF p. 13 (left- and right-hand typescript pages) and the Kleitman reference on PDF p. 16 (the list begins on PDF p. 14). Library home: Bermond 1983; paged at Bermond 1983, Section 6, the case Δ = 2 (PDF p. 13 of the deposit).
CGTT90: Chung, F. R. K., Gyárfás, A., Tuza, Z. and Trotter, W. T., The maximum number of edges in $2K_2$ -free graphs of bounded degree. Discrete Math. 81 (1990), no. 2, 129--135, doi:10.1016/0012-365X(90)90144-7 (the site's text prints no volume). Theorem 4, p. 131; the attribution, p. 129. Library home: Chung 1990 (the author's copy on W. T. Trotter's publication page); paged at Chung 1990, Theorem 4 (p. 131).
CCJK22: Cambie, S., Cames van Batenburg, W., de Joannis de Verclos, R. and Kang, R. J., Maximising line subgraphs of diameter at most $t$ . SIAM J. Discrete Math. 36 (2022), no. 2, 939--950, doi:10.1137/21M1437354 (the site's text spells "Maximizing"). Pages are those of arXiv:2103.11898v2 (10 December 2021, "v2 accepted to SIAM Journal on Discrete Mathematics", 12 pp.); the introduction, p. 1; Conjecture 1, Theorem 2, Conjectures 3--4 and Proposition 5, p. 2; Theorems 6--8 and Corollary 9, p. 3; Theorem 10, p. 4. Library home: Cambie 2022; paged at Cambie 2022, Theorem 6 (p. 3), Cambie 2022, Theorem 7 (p. 3), Cambie 2022, Theorem 2 (p. 2), Cambie 2022, Proposition 5 (p. 2), Cambie 2022, Conjecture 1 (p. 2), Cambie 2022, Conjecture 3 (p. 2) and Cambie 2022, Conjecture 4 (p. 2).
FGST89: Faudree, R. J., Gyárfás, A., Schelp, R. H. and Tuza, Zs., Induced matchings in bipartite graphs. Discrete Math. 78 (1989), 83--87; printed p. 83, the attribution of the $t=2$ question and value. Not a site key for this problem. Library home: Faudree 1989; paged at Faudree 1989, Problems (p. 83).
KMP26: Kumar, H., Mohar, B. and Pragada, S., An improved bound for the strong clique index of graphs. arXiv:2607.02698v1 (2 July 2026), 15 pp.; a preprint, cited at the pages of its arXiv PDF (Conjectures 1.9--1.10, Theorem 1.11 and Problem 1.12, p. 4; Lemma 3.1 and the $h_3(4)$ display, p. 9; Lemma 3.2's $h_3(15)$ display, p. 10; the "AI statement", p. 13). Library home: Kumar and Pragada 2026; paged at Kumar and Pragada 2026, Lemma 3.1 (p. 9) and Kumar and Pragada 2026, Theorem 1.11 (p. 4).
CvBK26: Cames van Batenburg, W. and Korsky, S., Asymptotically attaining the Moore bound. arXiv:2608.03965v1 (4 August 2026), "7+ε pages"; a preprint; its arXiv record (abstract only).

Problem 934

Status

Proof claims

Discussion