Graphs with degrees less than n/2
by
Brendan D. McKay
Australian National University
Coauthors: Ian M. Wanless, Nicholas C. Wormald

A problem of Vera Sös asks for the number of graphs on n vertices such that no vertex has degree more than n/2. Equivalently, what is the probability p(n) that a random graph has maximum degree at most n/2?

While one might naively expect p(n) to be close to 2^-n, in fact it is considerably larger. Riordan and Selby proved that p(n) = c^n+o(n) where c is a constant close to 0.61.

In this work, we prove that p(n)=c₀cⁿexp(c₁\surdn+o(1)), where c₀ and c₁ are two more constants. This is generalized to permit bounds on the maximum degree other than n/2.

Date received: November 10, 2000