For every fixed integer k≥ 2, there exists a constant C_k such that every graph G on n vertices with at least C_k n edges contains pairwise edge-disjoint cycles C_1,…,C_k satisfying V(C_k)⊆…⊆ V(C_1), and such that, for each i∈1,…,k-1, the cyclic order induced by C_i on V(C_i+1) agrees with the cyclic order induced by C_i+1, up to reversal.

Erdős’s nested-cycle problem

Erdős posed the two-cycle version in 1975: determine how many edges force two suitably nested, edge-disjoint cycles. The broader conjecture predicts a linear bound for every fixed number of nested cycles.

Known results

Bollobás, 1978: a linear bound for two nested cycles.
Chen, Erdős, and Staton, 1996: $O_k(n)$ edges force $k$ nested cycles when geometric noncrossing is not required.
For the geometric problem with $k\geq 3$ , the constant-average-degree case remains open, already for $k=3$ .
A prior general bound was $O_k\!\left(n(\log n)^{k-1}(\log\log n)^{k-3}\right)$ for fixed $k\geq 3$ .

September 2, 2026 reported improvement

A daily-news report states that the forcing number satisfies $O_k\!\left(n(\log\log n)^2/\log\log\log n\right)$ , equivalently $n(\log n)^{o(1)}$ , for fixed $k$ . This narrows the gap to the conjectured $O_k(n)$ bound, but the retrieved material does not independently verify the claim.

Current status (as of September 2026): The two-cycle case and the non-geometric multi-cycle case are settled, while the geometric conjecture $O_k(n)$ for fixed $k\geq 3$ remains open; the stronger subpolynomial bound is claimed but unverified.

Erdős’s nested-cycle problem

Primary source

Additional references

Progress summary

Solutions 0