# Enumerate non-isomorphic graphs on n vertices

In the following the graphs are assumed to be undirected and simple.

1.Enumerate the number of non-isomorphic graphs on $n$ vetrices where $n$ is fixed.

Here are some ideas I had:

The number of labeled graphs is $2^{\frac{n(n-1)}{2}}$.

So it is enough to find the number unlabeled graphs on $n$ vertices.I have no idea for this.

2.Enumerate the number of non-isomorphic graphs on $n$ vertices and $m$ edges where $n,m$ are fixed.

Can we find a closed formula for each of this?

Any help?

Thank you!

-
This is a rather difficult problem. See Sloane's oeis.org/A000088 which gives the number of graphs on $n$ vertices, and has many references. –  Grumpy Parsnip Jan 19 '12 at 20:22
"So it is enough to find the number unlabeled graphs on n vertices." The words non-isomorphic and unlabeled mean the same thing. –  Austin Mohr Jan 19 '12 at 21:34

## 2 Answers

See e.g. https://oeis.org/A000088 and references given there.

-
Great minds think alike. –  Grumpy Parsnip Jan 19 '12 at 21:35

For 1, you could use the Lemma that is not Burnside's.

-
You should add this as a comment, as it does not quite answer the question! –  Mariano Suárez-Alvarez Jan 19 '12 at 20:21
@DanielPietrobon: Is there a more elementary way? –  passenger Jan 19 '12 at 20:22
Dear passenger, Burnside's lemma is a little (but important) part in the solution of this problem. This is a classical, very difficult problem, and there is not much to hope for an "elementary way". –  Mariano Suárez-Alvarez Jan 19 '12 at 20:25