Hamilton cycles in 3-out

Tom Bohman, Alan Frieze

Published 2009-04-02, updated 2020-08-26Version 2

Let G_{\rm 3-out} denote the random graph on vertex set [n] in which each vertex chooses 3 neighbors uniformly at random. Note that G_{\rm 3-out} has minimum degree 3 and average degree 6. We prove that the probability that G_{\rm 3-out} is Hamiltonian goes to 1 as n tends to infinity.