# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:1612.06002

Discrete Mathematics, 122, 363-364, 1993.12
Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdős raised the question of determining $f(n)$ [see J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976; MR0411988 (54 #117)]. We prove that for $n\geq 36\cdot 5t^2-4\cdot 5t+1$ one has $f(n)\geq n+9t-1$ . We conjecture that $\liminf (f(n)-n)/\sqrt n\leq\sqrt 3$ .
maximum number of edges; graph; cycle
@inproceedings{lai1993on,
title={On the size of graphs with all cycle having distinct length},
author={Lai Chunhui},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227084359716230693},
booktitle={Discrete Mathematics},
volume={122},
pages={363-364},
year={1993},
}

Lai Chunhui. On the size of graphs with all cycle having distinct length. 1993. Vol. 122. In Discrete Mathematics. pp.363-364. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227084359716230693.