On random k ‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph G = ( V , E ) with large minimum degree. We fix a positive integer k and let G k be the random subgraph where each v ∈ V independently chooses k random neighbors, making kn edges in all. When the minimum degree δ ( G ) ≥ ( 1 2 + ε ) n ,   n = | V | then G k is k ‐connected w.h.p. for k = O ( 1 ) ; Hamiltonian for k sufficiently large. When δ ( G ) ≥ m , then G k has a cycle of length ( 1 − ε ) m for k ≥ k ε . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function ϕ ( n ) (or ϕ ( m ) ) wherelim n → ∞ ϕ ( n ) = 0 . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017