2026/07/02 by Micha Christoph, Alp Müyesser, Yuval Wigderson
#math.CO
The Erdős--Gallai theorem states that every graph of average degree d contains a cycle of length at least d. We prove the following robust extension of the Erdős--Gallai theorem: For every c>0 there exists K such that for all d≥ K, p≥ K/d and every graph G with average degree d, the random graph Gp obtained by independently sampling each edge of G with probability p contains a cycle of length at least (1-c)d asymptotically almost surely as |V(G)|→ ∞. With related methods, we prove the following hyperstability version of the Erdős--Gallai theorem: any graph G without a cycle of length at least d is at most c d|V(G)| edge deletions away from a graph all of whose connected components have a vertex-cover of size at most d. At the core of our argument lies a very general structure theorem about graphs that originates from results of Pokrovskiy concerning the hyperstability of bounded-degree trees.