Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph G of minimum degree at least k , let G p be a random subgraph of G obtained by taking each edge independently with probability p . We prove that (i) if p ≥ ω / k for a function ω = ω ( k ) that tends to infinity as k does, then G p asymptotically almost surely contains a cycle (and thus a path) of length at least ( 1 − o ( 1 ) ) k , and (ii) if p ≥ ( 1 + o ( 1 ) ) ln k / k , then G p asymptotically almost surely contains a path of length at least k . Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015