MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, does anyone know if it is known what is the number of undirected graphs with the following properties:

  • Number of nodes: $N$, a big number,
  • Average degree: $z_1$,
  • Average number of outgoing edges $z_2$, where an outgoing edges are all edges leaving one of your neighbors (except the one that connects you to that neighbor).


I interested in asymptotic results for large N.

Similarly, the entropy of an ensemble of graphs such that the average degree is $z_1$ and the average number of outgoing edges is $z_2$ is also of interest.

EDIT: The definition of $z_2$ is here: on section F, "Numbers of neighbors and average path length". Sorry for the loose definition. $z_2$ is also the number of second neighbors.


share|cite|improve this question
Are the nodes labelled, or not? (That is, are we counting up to isomorphism, or not?) – Graham Denham Jul 4 '11 at 19:54
Yes, the nodes are labelled. Sorry, I should have said this before. – Rorsa Jul 5 '11 at 14:19
Also, suppose v,w,and u are vertices of a triangle in the graph. How are the triangle edges weighted in the definition of z_2? I can see the edges counted once each or twice each. Gerhard "Email Me About System Design" Paseman, 2011.07.05 – Gerhard Paseman Jul 5 '11 at 21:20
If (v, w, u) is a triangle, the edge (w,u) is to be counted once in the set of "outgoing edges" of the node v. – Rorsa Jul 6 '11 at 23:00

I do not understand what your outgoing edges are but the number of undirected graphs with $N$ labeled vertices and average degree $d$ (which you call $z_1$ but $d$ seems more natural to me) is approximatively given by $${2^{N(N-1)/2}\choose dN/2}$$ since this is the number of all possible adjacency matrices.

The asymptotics for fixed $d$ and $N\rightarrow\infty$ are then given by $$2^{dN^2(N-1)/4}\frac{1}{(dN/2)!}$$ which can be made more explicit using Stirling's formula.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.