Problem Statement
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$.
Categories:
Graph Theory Cycles
Progress
A problem of Erdős, Duke, and Rödl. Duke and Erdős [DuEr83], who proved the first if $n$ is sufficiently large depending on $\delta$. The real challenge is to prove this when $\delta=n^{-c}$ for some $c>0$. Duke, Erdős, and Rödl [DER84] proved the first statement with a $\delta^5$ in place of a $\delta^3$.Fox and Sudakov [FoSu08b] have proved the second statement when $\delta >n^{-1/5}$.
See also the entry in the graphs problem collection.
Source: erdosproblems.com/584 | Last verified: January 15, 2026