enumerating graphs
How many graphs are there?
Proposition 1.
The number of nonisomorphic simple graphs^{} on $N$ vertices, denoted $g\mathit{}p\mathit{}h\mathit{}\mathrm{(}N\mathrm{)}$, satisfies
$$\frac{{2}^{\left(\genfrac{}{}{0pt}{}{N}{2}\right)}}{N!}\le gph(N)\le {2}^{\left(\genfrac{}{}{0pt}{}{N}{2}\right)}.$$ 
Proof.

($\le $)
Every simple graph on $N$ vertices can be encoded by a $N\times N$ symmetric matrix^{} with all entries from $\{0,1\}$ and with $0$’s on the diagonal^{}. Therefore the information can be encoded by strictly upper triangular $N\times N$ matrices over $\{0,1\}$. This gives ${2}^{\left(\genfrac{}{}{0pt}{}{N}{2}\right)}$ possibilities.

($\ge $)
The number of isomorphisms^{} from a graph $G$ to a graph $H$ is equal to the number of automorphisms of $G$ (or $H$). Therefore the total number of isomorphisms between two graphs is no more than $N!$ – the total number of permutations^{} of the $N$ vertices of $G$. Therefore the total number of nonisomorphic simple graphs on $N$ vertices is at least ${2}^{\left(\genfrac{}{}{0pt}{}{N}{2}\right)}/N!$.
∎

•
The gap between the bounds is superexponential in $N$: that is: $O\left({2}^{\left(\genfrac{}{}{0pt}{}{N}{2}\right)}\right)$. However logarithmically the estimate is tight:
$$\mathrm{log}gph(N)\in \mathrm{\Omega}({N}^{2}N\mathrm{log}N)\cap O({N}^{2})=\mathrm{\Theta}({N}^{2}).$$ 
•
$gph(N)$ is closer to the lower bound; yet, most graphs have few automorphisms.

•
$gph$ is monotonically increasing.
$$
References
 1 Harary, Frank and Palmer, Edgar M. Graphical enumeration Academic Press, New York, 1973, pp. xiv+271, 05C30, MR MR0357214 (50 #9682)
Title  enumerating graphs 

Canonical name  EnumeratingGraphs 
Date of creation  20130322 15:50:07 
Last modified on  20130322 15:50:07 
Owner  Algeboy (12884) 
Last modified by  Algeboy (12884) 
Numerical id  6 
Author  Algeboy (12884) 
Entry type  Theorem 
Classification  msc 05C30 
Related topic  EnumeratingGroups 