# Enumerating all simple graphs

Is there a way to (efficiently) enumerate all simple graphs with a given number of vertices up to isomorphism? That is, I don't care about the degeneracy of a graph, only the set of isomorphicly isomorphically unique ones of a given size.

-
In a class I took last spring one of the term projects was on this, his final results are here wiki.ucfilespace.uc.edu/groups/combgen/wiki/972b8/… . – JSchlather Dec 13 '10 at 18:29
This is a difficult problem, which I am sure is exponentially difficult. For low numbers of vertices one can rely on various graph invariants, but in general this is quite complex. I've encountered this issue in calculating bases for "graph homology," but the number of isomorphism classes of graphs blows up quickly. – Grumpy Parsnip Dec 13 '10 at 21:47
@Jacob: I like your output. It would be even nicer if you just kept the connected graphs, and tried to present the graphs planarly, if possible, or minimizing intersections! – Mariano Suárez-Alvarez Jan 3 '11 at 3:32

Since almost all graphs have a trivial automorphism group, there are asymptotically $2^{n \choose 2}/n!=O(2^{n^2})$ non-isomorphic graphs.
Suppose you could encode each graph using 1 bit (of course you can't actually do this, but this will help give a lower bound on the complexity). If the input string $n$ is encoded using $O(\log n)$ bits, then merely writing a "1" for each non-isomorphic graph would require at least double-exponential time $O(2^{(2^{\log n})^2})=O(2^{2^{2 \log n}})$.