Problem

Source: RMM 2019

Tags: RMM, RMM 2019, combinatorics, graph theory, cycles, Fedya, probability



Given any positive real number $\varepsilon$, prove that, for all but finitely many positive integers $v$, any graph on $v$ vertices with at least $(1+\varepsilon)v$ edges has two distinct simple cycles of equal lengths. (Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.) Fedor Petrov, Russia