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.
