← All problems

Erdős Problem #585 — Edge-disjoint cycles on the same vertex set

51 years old · traced to

For a positive integer nn, let GG range over finite simple undirected graphs with ∣V(G)∣=n|V(G)|=n. A cycle means a simple cycle, and two cycles are edge-disjoint if they share no edges. Define Chakraborti, Janzer, Methuku, and Montgomery (2025)

M(n)=max⁡{∣E(G)∣:G contains no two edge-disjoint cycles with the same vertex set}.M(n)=\max\bigl\{|E(G)|: G\text{ contains no two edge-disjoint cycles with the same vertex set}\bigr\}.

Chakraborti, Janzer, Methuku, and Montgomery (2025)

The question is to determine M(n)M(n), the largest possible number of edges under this prohibition. Chakraborti, Janzer, Methuku, and Montgomery (2025)

Background

Erdős posed this extremal question in 1975. A lower bound comes from a construction of Pyber, Rödl, and Szemerédi: their graphs have Ω(nlog⁡log⁡n)\Omega(n\log\log n) edges and no 44-regular subgraph. Since the union of two edge-disjoint cycles on the same vertex set is 44-regular on that set, these graphs contain no forbidden pair. This connects the problem to the Erdős–Sauer problem on forcing regular subgraphs, though absence of a 44-regular subgraph is a sufficient construction criterion, not an equivalent reformulation of the cycle condition. Chakraborti, Janzer, Methuku, and Montgomery (2025)

Before the direct approach of Chakraborti, Janzer, Methuku, and Montgomery, upper bounds came from Turán-type results: for example, the Kővári–Sós–Turán theorem gives O(n7/4)O(n^{7/4}), while later developments using blow-ups of cycles give n3/2+o(1)n^{3/2+o(1)}. The paper explains that this general Turán approach cannot improve the exponent below 3/23/2, making a direct method important for closing the gap with the nlog⁡log⁡nn\log\log n construction. Chakraborti, Janzer, Methuku, and Montgomery (2025)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.