Problem 585

What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?

Source: erdosproblems.com/585

Graph theory
Cycles

Wiki page

Status

Open

No claim settles this problem.

Open. The maximum is known only up to a polylogarithmic factor. Lower bound: the Pyber--Rödl--Szemerédi graphs with $\Omega(n\log\log n)$ edges and no $k$ -regular subgraph for any $k\ge3$ have no two edge-disjoint cycles on the same vertex set (Theorem 1 of the 1995 paper, printed p. 42, whose concluding remarks on p. 53 place this problem's class under it; recorded below). Upper bound: Theorem 2 of Chakraborti, Janzer, Methuku and Montgomery (Chakraborti et al. 2024) (Adv. Math. 469 (2025), refereed; cited from the arXiv v1): for some absolute $t$ and every $k\ge2$ there is $c(k)$ such that $c(k)\,n(\log n)^t$ edges force $k$ pairwise edge-disjoint cycles with the same vertex set, so the maximum is $O(n(\log n)^t)$ ; the exponent $t$ is not made explicit. The authors ask whether their bound improves to $O_k(n\log\log n)$ . No exact value, asymptotic formula or matching pair of bounds was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

CJMM24: Chakraborti, D. and Janzer, O. and Methuku, A. and Montgomery, R., Edge-disjoint cycles with the same vertex set. arXiv:2404.07190 (v1 10 April 2024, the version cited; the only arXiv version); Adv. Math. 469 (2025), Paper No. 110228, doi:10.1016/j.aim.2025.110228 (not held, not compared). Problem 1 and Theorem 2, p. 2. Library home: Chakraborti et al. 2024.
PRS95: Pyber, L. and Rödl, V. and Szemerédi, E., Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63 (1995), 41--54, doi:10.1006/jctb.1995.1004 (the site's reference list titles it "Dense subgraphs without 3-regular subgraphs"). Theorem 1 and the König remark, printed p. 42; the proof, pp. 42--46; the concluding remark on $ex(n,C^2)$ , p. 53. Library home: Pyber and Szemerédi 1995 paged at Pyber and Szemerédi 1995, Theorem 1. Its theorem is also quoted on p. 2 of [CJMM24], as Theorem 1.1 of [JaSu23] and as Theorem 1.2 of [CJMM24b].
Er76b: Erdős, P., Problems and results in graph theory and combinatorial analysis. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congr. Numer. XV (1976), 169--192; Problem 29, p. 191. Library home: Erdős 1976 (the Rényi archive's scan).
JaSu23: Janzer, Oliver and Sudakov, Benny, Resolution of the Erdős-Sauer problem on regular subgraphs. Forum Math. Pi 11 (2023), Paper No. e19; Theorem 1.1 (Pyber--Rödl--Szemerédi, quoted), p. 2. Library home: Janzer and Sudakov 2023.
CJMM24b: Chakraborti, D., Janzer, O., Methuku, A. and Montgomery, R., Regular subgraphs at every density. arXiv:2411.11785 (v2 26 November 2025, the version cited); Trans. Amer. Math. Soc., doi:10.1090/tran/9694 (online 18 August 2026; not held). Theorem 1.2 (Pyber--Rödl--Szemerédi, quoted), p. 2. Library home: Chakraborti et al. 2024.
CES96: Chen, G., Erdős, P. and Staton, W., Proof of a conjecture of Bollobás on nested cycles. J. Combin. Theory Ser. B 66 (1996), 38--43. Not held; quoted on p. 2 of [CJMM24] for the bound $O(n^{7/4})$ .
Ja23: Janzer, O., Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles. Israel J. Math. 253 (2023), 813--840. Not held; quoted on p. 2 of [CJMM24] for the bound $n^{3/2+o(1)}$ .
JSS24: Janzer, B., Steiner, R. and Sudakov, B., Chromatic number and regular subgraphs. Bull. London Math. Soc. 58 (2026), e70262, doi:10.1112/blms.70262; arXiv:2410.02437 (v1 3 October 2024). Context only, on a chromatic-number version of the same configuration. Library home: Janzer, Steiner and Sudakov 2025.

Problem 585

Status

Proof claims

Discussion