# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:2110.06001

Discrete Applied Mathematics, 337, 42-45, 2023.10
In 1975, P. Erd\H os proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n.$ \par We make the following conjecture: \par \bigskip \noindent{\bf Conjecture.} $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$
graph, cycle, number of edges
@inproceedings{lai2023an,
title={An old problem of Erd\H os: a graph without two cycles of the same length},
author={Lai Chunhui},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20211013142626071808877},
booktitle={Discrete Applied Mathematics},
volume={337},
pages={42-45},
year={2023},
}

Lai Chunhui. An old problem of Erd\H os: a graph without two cycles of the same length. 2023. Vol. 337. In Discrete Applied Mathematics. pp.42-45. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20211013142626071808877.