# 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. – Cheerful 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

## 1 Answer

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

• Great minds think alike. – Cheerful Parsnip Jan 19 '12 at 21:35