Pancyclic subgraphs of random graphs

An n ‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤ t ≤ n . In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p > n −1/2 , then the random graph G ( n, p ) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G ( n, p ) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.