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}$$


$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:

A. Is there an answer already found for this question?

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.

  • 1
    $\begingroup$ Get the first few values, then look 'em up at the Online Encyclopedia of Integer Sequences. $\endgroup$ Jun 3 '11 at 22:28
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Jun 3 '11 at 23:12
  • 2
    $\begingroup$ 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? $\endgroup$
    – fedja
    Jun 4 '11 at 0:28
  • $\begingroup$ 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. $\endgroup$
    – malloc8
    Jun 4 '11 at 1:03
  • $\begingroup$ See mathoverflow.net/questions/68017/… $\endgroup$
    – Tony Huynh
    Feb 11 '20 at 14:28

Start here and you might find more.



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.