Problem 584

Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that $H_1$ has $\gg \delta^3n^2$ edges and every two edges in $H_1$ are contained in a cycle of length at most $6$ , and furthermore if two edges share a vertex they are on a cycle of length $4$ , and $H_2$ has $\gg \delta^2n^2$ edges and every two edges in $H_2$ are contained in a cycle of length at most $8$ .

Source: erdosproblems.com/584

Graph theory
Cycles

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (OPEN), for a statement that no finite computation can settle; page last edited 22 January 2026. Under the reading the Formulation adopts, the first clause with $\delta^3$ is proved for no $c>0$ , and only with $\delta^5$ in place of $\delta^3$ for every $0<c<1/2$ (Duke, Erdős and Rödl 1984, Theorem 3), while the second clause is proved for every $c<1/5$ (Fox--Sudakov 2008, refereed) and claimed for every $c\le1/3$ by a 2026 preprint announced on the thread [Li26] (Li 2026); the $\delta^3$ version of the first clause has been open since 1984. Under the fixed- $\delta$ reading both clauses are answered: the first by Duke and Erdős's Corollary 1 (1982), with the cubic dependence only as a remark of 1984, and the second by a result Duke, Erdős and Rödl state without proof in their 1992 paper [DER92], whose proof Fox and Sudakov attribute to a 1991 proceedings paper [DER91] that is not held. Three results concern ranges of $c$ bounded away from $0$ and settle no instance of the adopted question: Fox and Sudakov's remark that the second clause fails for $\beta$ close to $1$ , the girth-10 counterexamples of a note of 21 April 2026 posted on the thread [Ch26], which fail it for every $4/5<\beta<1$ , and the obstruction of [Li26] to the first clause for $\delta=n^{-\beta}$ , $1/3\le\beta<1/2$ . They are recorded in the Current assessment and have no claim pages; no result settles the first clause, so the standing derives as open.

DuEr82: Duke, Richard and Erdős, Paul, Subgraphs in which each pair of edges lies in a short common cycle. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 253--260. Theorem 1, pp. 253--254; Corollary 1, p. 255; remark, p. 258. Library home: Duke and Erdős 1982 (a scan).
DER84: Duke, Richard and Erdős, Paul and Rödl, Vojtěch, More results on subgraphs with many short cycles. Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), Congr. Numer. 43 (1984), 295--300. Theorem 1, p. 296; Theorem 2, p. 298; Theorem 3, p. 299; remark, p. 295. Library home: Duke, Erdős and Rödl 1984 (a scan).
FoSu08b: Fox, Jacob and Sudakov, Benny, On a problem of Duke-Erdős-Rödl on cycle-connected subgraphs. J. Combin. Theory Ser. B 98 (2008), no. 5, 1056--1062; doi:10.1016/j.jctb.2007.12.003 (received 10 April 2007, available online 8 February 2008). Problem 1.1 and Theorem 1.2, p. 1057. Library home: Fox and Sudakov 2008.
DER91: Duke, R. A., Erdős, P. and Rödl, V., Extremal problems for cycle-connected graphs. Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, La., 1991), Congr. Numer. 83 (1991), 147--151. Not held and not cited by the site; known only through p. 1057 of [FoSu08b].
DER92: Duke, R. A., Erdős, P. and Rödl, V., Cycle-connected graphs. Discrete Math. 108 (1992), no. 1--3, 261--278; doi:10.1016/0012-365X(92)90680-E (received 4 January 1991). Not cited by the site. Fixed-density statement and the set-system Theorem, p. 262; recalled bounds (1)--(3), p. 263; concluding remarks, p. 277. Library home: Duke and Rödl 1992 (the publisher's open-archive edition).
Li26: Li, Eric, On the Duke--Erdős--Rödl problem at the one-third threshold. arXiv:2606.06522v1 (2 June 2026), 20 pp.; preprint, not held, described from its arXiv abstract; announced on the discussion thread by its author on 10 June 2026. Claim page Li 2026.
Ch26: A note on the formulation of Erdős Problem #584, a five-page note dated "April 21, 2026", naming no author in its text, hosted at https://www.ulam.ai/research/erdos584.pdf and linked from the discussion thread on 21 April 2026 by a post that credits it to GPT-5.4 Pro. Theorem 1, Corollary 2 and Remark 3, p. 2; Proposition 4 and Remark 5, pp. 3--4. Not filed: unrefereed, and its mathematics is recorded in the Current assessment, not as a claim page.
Be66: Benson, C. T., Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 (1966), 1091--1094. Not held; the reference [3] that p. 1061 of [FoSu08b] cites for graphs with $n^{2-\beta}$ edges and no $8$ -cycle.
LUW95: Lazebnik, F., Ustimenko, V. A. and Woldar, A. J., A new series of dense graphs of high girth. Bull. Amer. Math. Soc. (N.S.) 32 (1995), 73--79. Not held; the source of the graphs $CD(5,q)$ that Theorem 1 of [Ch26] uses.

Problem 584

Status

Proof claims

Discussion