Some Open Problems on Cycles

Abstract

Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. Erdős raised the problem of determining $f(n)$. Erdős conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\ge c{n}^{1+\frac{1}{k}}$. Hajós conjectured that every simple even graph on $n$ vertices can be decomposed into at most $\frac{n}{2}$ cycles. We present the problems, conjectures related to these problems, and we summarize the known results. We do not think Hajós’ conjecture is true.