Problem 585

Erdős Problem #585: declared status 'open'. Formalized: no. 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? Current best: Indeed, they prove that there exists a constant $C>0$ such that for any $k\geq 2$ there is a $c_k$ such that if a graph has $n$ vertices and at least $c_kn(\log n)^{C}$ many edges then it contains $k$ pairwise edge-disjoint cycles with the same vertex set. Prize: no. Tags: cycles, graph theory.