The probability of connectedness of a large unlabelled graph
Elizabeth Mary Wright · Bulletin of the American Mathematical Society · 1973
An (n, q) graph is one with n nodes and q edges, in which any two different nodes are or are not joined by a single edge. We write T = T(n, q) for the number of different (n, q) graphs with unlabelled nodes and t for the number of these graphs which are connected, so that p = t/T is the probability that an unlabelled (n, q) graph is connected. We write F, ƒ and a for the corresponding numbers for (n, q) graphs whose nodes are labelled. We write also N = n(n l)/2, B(h,k) = h\/{k\(h *)!} and y = (2q — n log n)/n. Clearly q g N. In what follows, A (not always the same at each occurrence) is a fixed positive number at our choice and all statements are true only for n > n0, q > q0, where n0 and q0 depend on the A. Erdos and Renyi [1] put q = [n(log n + a)/2], where a is independent of n and q, and showed that, for these q, we have