MathSciDoc: An Archive for Mathematician ∫

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\"{o}s raised the problem of determining $f(n)$. Erd\"{o}s conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$. Haj\'{o}s conjecture that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj\'{o}s conjecture is true.

Haj\'{o}s conjecture; even graph; Turan number; cycle; the maximum number of edges