All the Moments of the Vertex Degrees of Randomly Generated Graphs

Doron ZEILBERGER ^{1}

Consider the set of all labelled graphs on n vertices and m edges. By the handshaking lemma the average degree of every graph is 2m/n. Higher moments do depend on the graph, but one can easily compute the average of the average of \binom{deg(v)}{k}, for any k. Let N = n(n − 1)/2. The answer is \binom{n−1}{k}\binom{N−k}{m−k}/\binom{N}{m}, which equals the rational funcion (in n and m) \binom{n−1}{k}(m − k + 1)_{k}/(N − k + 1)_{k}, where as usual (a)_{k} := a(a+1) ⋯ (a+k−1). Indeed, for any particular vertex v, the sum of \binom{deg(v)}{k} over all graphs with n vertices and m edges counts such graphs with a k-subset of v’s neighbors marked. Clearly the number of these marked graphs is \binom{n−1}{k}\binom{N−k}{m−k}, (the first term for choosing the marked neighbors and the second term for choosing the remaining edges. From this it is easy to compute any desidred moment.

The special case k = 2 yields a one-line proof of the result in Ivan Gutman and Peter Paule, Univ. Beograd. Publ. Elek. Fak. 13 (2002), 30-35. [http://mathematika.etf.bg.ac.yu/publikacije/].

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. http://www.math.rutgers.edu/~zeilberg/ . Dec. 1, 2003. Exclusive to the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html . Supported in part by the NSF. Version of May 9, 2005 [correcting a typo pointed out by Mohamud Mohammed].