<p>See <a href="http://oeis.org/A054924" rel="nofollow">OEIS sequence A054924</a> for discussion and references.</p>

<p>As far as I know this grows faster than any polynomial.  In particular, see the <a href="http://oeis.org/A001437" rel="nofollow">sequence of the largest value of |G(n,m)|</a> for each $n$.</p>

CC BY-SA 2.5
2011-04-05T09:51:30.780Z
2011-04-05T09:51:30.780Z
András Salamon
<p>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 ! </p>

<p>Of course, you can break those "natural assumptions" by setting $m = 0$, or $m&lt;n-1$ in your case...</p>

<p>Nathann</p>

CC BY-SA 2.5
2011-04-05T09:50:28.763Z
2011-04-05T11:58:07.993Z
2011-04-05T11:58:07.993Z
Nathann Cohen
<p>Let $G( n, m )$ be the set of all possible <b>connected</b> 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 <b>non-isomorphic</b>.</p>

<blockquote>
  <p><strong>Question</strong>  </p>
  
  <p>How large can $|G( n, m )|$ be? Is it polynomial in both $n$ and $m$? Or is it superpolynomial in either $n$ or $m$?</p>
</blockquote>

<graph-theory><co.combinatorics><graph-isomorphism>
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
Giorgio Camerani
# Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges

(Asked by: username_0 on 2011-04-05)

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

**Tags:** graph-theory, co.combinatorics, graph-isomorphism


---

## 2 answers

### Answer by username_2 on 2011-04-05. Score: 8 | Accepted answer

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

Nathann


---

### Answer by username_1 on 2011-04-05. Score: 5

See [OEIS sequence A054924](http://oeis.org/A054924) for discussion and references.

As far as I know this grows faster than any polynomial. In particular, see the [sequence of the largest value of |G(n,m)|](http://oeis.org/A001437) for each $n$.


---

