An (n, q) graph consists of n labelled nodes and q edges, i.e. unordered pairs of different nodes. The maximum possible value of q is N = ½n(n − 1) and the (n, N) graph is the complete graph. We write B(h, k) = h!/{k!(h − k)!}. The number of (n, q) graphs is clearly B(N, q). A k-cycle in a graph consists of a sequence

of k edges, where D1D2,…, Dk are all different nodes. We are concerned here with the probability P = P(n, q, k) that a k-cycle will be present in an (n, q) graph, that is, the proportion of all (n, q) graphs which contain at least one k-cycle. We investigate the limit of P as n → ∞ and in particular try to determine when P → 1 (when we say that almost all (n, q) graphs contain a k-cycle) and when P → 0 (when we say that almost no (n, q) graphs contain a k-cycle).