Lower Bound on the Number of Graph Isomorphism Classes Are there any non-trivial lower bounds on the number of isomorphism classes for a graph with $N$ vertices?
For example there are at least $N(N-1)/2$ isomorphism classes (counting one for the number of possible edges in our graph) but as $N$ increases, there will clearly be a lot more.

You really need to say what you mean by non-trivial. What do you want to use the bound for? But, gripes aside, $2^{\binom{n}2}/n!$ is a lower bound and asymptotically tight.
