Combinatorics, Probability and Computing

The Maximum Degree of a Random Graph

a1 Trinity College, Cambridge CB2 1TQ, England
a2 Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England


Let 0 < p < 1, q = 1 − p and b be fixed and let G [set membership] [script G](n, p) be a graph on n vertices where each pair of vertices is joined independently with probability p. We show that the probability that every vertex of G has degree at most pn + b [surd radical]npq is equal to (c + o(1))n, for c = c(b) the root of a certain equation. Surprisingly, c(0) = 0.6102 … is greater than [fraction one-half] and c(b) is independent of p. To obtain these results we consider the complete graph on n vertices with weights on the edges. Taking these weights as independent normal N(p, pq) random variables gives a ‘continuous’ approximation to [script G](n, p) whose degrees are much easier to analyse.

(Received April 21 1999)
(Revised March 30 2000)