# Number of graphs with $n$ edges

I have been trying to count the number of graphs up to isomorphism which are:

1. Simple
2. Connected
3. Have $$n$$ edges.

I apologize in advance if there is ample documentation on this question; however, I have found none. Thus far, my best overestimate is: $$g(n) = \sum_{i=x}^y t(i) \cdot \binom{a(i)} { n - i - 1}$$

where:

$$g(n) :=$$ the number of such graphs with $$n$$ edges,

$$t(i) :=$$ the number of trees up to isomorphism on $$i$$ vertices,

$$a(i) :=$$ the number of non-adjacent vertices in a tree on $$i$$ vertices.

I have conjectured that: $$a(i) = \sum_{k-1}^i (i - k), \qquad y = n+1,\quad\text{and}$$ $$x \geq$$ the number of vertices in the complete graph with the closest number of edges to $$n$$, rounded down.

I have also read that the number of trees including isomorphism with $$i$$ vertices is $$i^{i-2}$$, and have placed that as the upper bound for $$t(i)$$.

And that [according to Wikipedia] there is an estimate for the number of such trees up to isomorphism: $$t(i)\sim C \alpha^i i^{-5/2}$$ with $$C=0.534949606...$$ and $$\alpha=2.99557658565...$$.

What I would like to know is:

B. Is there any information off the top of your head which might assist me?

C. Is this problem incredibly hard?

Again, I apologize if this is not appropriate for this site. I am a sophomore undergraduate student, and I have been trying to answer or estimate this question for use as an upper bound for another larger question that I am working on.

Thanks for the help.

• Get the first few values, then look 'em up at the Online Encyclopedia of Integer Sequences. Jun 3 '11 at 22:28
• A. I doubt an exact number is known but I am pretty sure the question has been asked before and there is a lot of literature; B the rough order is $e^{n\log n}$ (give or take a constant factor in the exponent). C. That depends on the precision you want. The crude estimate I quoted is trivial but the more accurate bounds you want, the harder it gets. Jun 3 '11 at 23:12
• It is certainly not the state of the art but a quick literature search yields the asymptotics $\left[\frac 2e\frac n{\log^2 n}\gamma(n)\right]^n$ with $\gamma(n)=1+c(n)\frac{\log\log n}{\log n}$ and $c(n)$ eventually between $2$ and $4$. Is it good enough for your purposes? Jun 4 '11 at 0:28
• Thanks for your help. This will be enough to place an upper bound on what I was looking for, though I'm afraid I vastly underestimated the order of magnitude. Because of this, I doubt I'll be able to use this to produce a close estimate. For anyone interested in further pursuing this problem on it's own. If there is an estimate available for the average number of spanning trees in an n-vertex simple graph, I believe dividing the sum that I proposed: g(n) = The sum (t(i) * (a(i) choose (n - i - 1))) from i=x to y by a manipulation of this number may provide an estimate. Jun 4 '11 at 1:03
• Feb 11 '20 at 14:28