My problems first:
- An upper bound or lower bound for the number of non-isomorphic-$n$-point graphs
- Construct explicitly as many as possible of them
This originates from the homework, and I am sure that it is an open question. The original purpose is to construct at least $n^2$ of them, which is not that hard by considering 'hairy cycles'. By 'hairy cycles', I mean a cycle $C_{m}$ and one or two edges $e_{1}(,e_{2})$, whose one endpoint is in $C_{m}$, and the other one not in $C_{m}$. This is enough because I may vary the size of the cycle and the relative position of the two edges.
I have looked up the sequence at OEIS, and seemingly it grows in exponential speed (probably larger than that)! However, my method even fails to construct $O(n^3)$ of them. Hopefully, these have explained my motivation for this problem.
Some easy estimates:
The number of labelled graphs on $n$ vertices $1$, $2$, $\ldots$, $n$, equals $2^{\binom{n}{2}}$. The group $S_n$ acts on this set. The number of orbits is the number of non-isomorphic graphs with $n$ vertices. Now, every orbit has at most size $n!$ ( possibly smaller if the graph has a non-trivial group of isomorphisms). Conclusion: there are at least $$\frac{2^{\binom{n}{2}}}{n!}$$ of isomorphism classes of graphs with $n$ vertices. This is a fairly poor estimate, but it shows that for the $N_n$ number of graphs on $n$ vertices we have $\log N_n \simeq n^2$.