Erdős and Rényi (1960) showed that for many monotone-increasing properties of random graphs, graphs of a size slightly less than a certain threshold are very unlikely to have the property, whereas graphs with a few more graph edges are almost certain to have it. This is known as a phase transition (Janson et al. 2000, p. 103).
Erdős, P. and Rényi, A. "On the Evolution of Random Graphs." Publ. Math. Inst. Hungar. Acad. Sci.5, 17-61, 1960.Janson, S.; Łuczak, T.; and Ruciński, A. "The Phase Transition." Ch. 5 in Random Graphs. New York: Wiley, pp. 103-138, 2000.
