Edge-disjoint cycles with the same vertex set

In 1975, Erdős asked for the maximum number of edges that an n -vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turán-type results can be used to prove an upper bound of n 3 / 2 + o ( 1 ) . However, this approach cannot give an upper bound better than Ω ( n 3 / 2 ) . We show that there is an absolute constant t and some constant c = c ( k ) such that for each k ≥ 2 , every n -vertex graph with at least c n ( log ⁡ n ) t edges contains k pairwise edge-disjoint cycles with the same vertex set, resolving this old problem in a strong form up to a polylogarithmic factor. The well-known construction of Pyber, Rödl and Szemerédi of graphs without 4-regular subgraphs shows that there are n -vertex graphs with Ω ( n log ⁡ log ⁡ n ) edges which do not contain two cycles with the same vertex set, so the polylogarithmic term in our result cannot be completely removed. Our proof combines a variety of techniques including sublinear expanders, absorption and a novel tool for regularisation, which is of independent interest. Among other applications, this tool can be used to regularise an expander while still preserving certain key expansion properties.