# How many different non-isomorphic random graphs of the Erdős–Rényi model exist?

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)$$?

• The following MSE link might prove useful. – Marko Riedel Aug 5 '19 at 15:13
• Are you interested in exact or asymptotic results? – Misha Lavrov Aug 5 '19 at 15:52
• 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. – 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.