A lower bound for the number of edges in a graph containing no two cycles of the same length (Q5950392): Difference between revisions

The author improves on his own older results on the maximum number \(f(n)\) of edges in a graph of order \(n\) in which any two cycles are of different length. The problem of determining \(f(n)\) was posed by Erdős in 1975. Using a complicated explicit construction, the author establishes that \(\liminf_{n\to\infty}\frac{f(n)-n}{\sqrt{n}}\geq \sqrt{2+\frac{2562}{6911}}\approx 1.5397\).