In what models of random graphs is it true that almost every graph is Hamiltonian? In particular, how large does M(n) have to be to ensure that a.e. GM is Hamiltonian? This is one of the important questions Erdős and Rényi (1961a) raised in their fundamental paper on the evolution of random graphs. After several preliminary results due to Palásti (1969a, b, 1971a, b), Perereplica (1970), Moon (1972d), Wright (1973a, 1974b, 1975b, 1977b), Komlós and Szemerédi (1975), a breakthrough was achieved by Pósa (1976) and Korshunov (1976). They proved that for some constant c almost every labelled graph with n vertices and at least cn log n edges is Hamiltonian. This result is essentially best possible since even almost sure connectedness needs more than ½n log n edges. A great many extensions and improvements of the Korshunov–Pósa result above have been proved by D. Angluin and Valiant (1979), Korshunov (1977), Komlós and Szemerédi (1983), Shamir (1983, 1985), Bollobás (1983a, 1984a), Bollobás, Fenner and Frieze (1987), Bollobás and Frieze (1987) and Frieze (1985b).

Another basic problem concerns the maximal length of a path in Gc/n, where c is a constant. We know that for c > 1 a.e. Gc/n contains a giant component—in fact a component of order {1 – t(c) + o(1)}n—but the results of Chapter 6 tell us nothing about the existence of long cycles.