The Erdős–Rényi model $G(n,m)$ gives a random graph on n vertecies with m edges. I'm interested in the number of possible graphs, that can be generated that way.

If you ignore isomorphism, there are quite obvious $nCr(\frac{n(n-1)}{2}, m)$ possible graphs.

From my intuition these graphs should have lot's of isomorphic "copies", which are counted as well. So how many "truly diffrent" (not isomorphic to another) graphs do exist for $G(n.m)$?

  • $\begingroup$ The following MSE link might prove useful. $\endgroup$ – Marko Riedel Aug 5 '19 at 15:13
  • $\begingroup$ Are you interested in exact or asymptotic results? $\endgroup$ – Misha Lavrov Aug 5 '19 at 15:52
  • $\begingroup$ I'm mainly interested in exact results (or bounds) for relative small n,m than in an asymptotic outcome, but if you have something regarding the later I'd happily look into it as well. $\endgroup$ – Simoris Aug 5 '19 at 15:58

Since $G(n,m)$ may produce every graph on $n$ vertices and with $m$ edges, you seem to be simply asking about the number of non-isomorphic graphs with these numbers of vertices and edges. This sounds like a difficult counting problem, but it appears that there is, in fact, a (complicated) closed formula for this number, see this answer on MathOverflow. For concrete examples, see this sequence on OEIS.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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