Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-isomorphic.Question How large can $|G( n, m )|$ be? Is it polynomial in both $n$ and $m$? Or is it superpolynomial in either $n$ or $m$?
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
graph theory;co.combinatorics;graph isomorphism
According to Bollobas (Random Graphs), if you make natural assumptions on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ vertices and $m$ edges, so roughly $\frac{1}{n!}{{n \choose 2} \choose m}$ unlabelled graphs on $n$ vertices and $m$ edges. If you pick something like $m = \frac{1}{2}{n \choose 2}$, all those graphs should be connected with high probability, so I'd say --> massively superpolynomial ! Of course, you can break those natural assumptions by setting $m = 0$, or $m<n-1$ in your case...Nathann