4
$\begingroup$

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!

  • 2
    This is a rather difficult problem. See Sloane's http://oeis.org/A000088 which gives the number of graphs on $n$ vertices, and has many references.2012-01-19
  • 1
    "So it is enough to find the number unlabeled graphs on n vertices." The words *non-isomorphic* and *unlabeled* mean the same thing.2012-01-19

1 Answers 1