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 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.

• 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 non-isomorphic 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:

  $$\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.

Title	enumerating graphs
Canonical name	EnumeratingGraphs
Date of creation	2013-03-22 15:50:07
Last modified on	2013-03-22 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