enumerating graphs

How many graphs are there?

Proposition 1.

The number of non-isomorphic 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.

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

• The number of isomorphisms from a graph $G$ to a graph $H$ is equal to the number ofautomorphisms of $G$ (or $H$). Therefore the total number of isomorphisms between twographs is no more than $N!$ – the total number of permutations of the $N$ vertices of$G$. Therefore the total number of non-isomorphic simple graphs on $N$ vertices isat 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:

  $$\log gph(N)\in \mathrm{\Omega }(N^2-N\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.