enumerating graphs

How many graphs are there?

The number of non-isomorphic simple graphs on $N$ vertices, denoted $gph(N)$ , satisfies

\frac{2^{\binom{N}{2}}}{N!}\leq gph(N)\leq 2^{\binom{N}{2}}.

( $\leq$ )

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^{\binom{N}{2}}$ possibilities.
( $\geq$ )

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^{\binom{N}{2}}/N!$ .

∎

•

The gap between the bounds is superexponential in $N$ : that is: $O\left(2^{\binom{N}{2}}\right)$ . However logarithmically the estimate is tight:

$\log gph(N)\in\Omega(N^{2}-N\log N)\cap O(N^{2})=\Theta(N^{2}).$
•

$gph(N)$ is closer to the lower bound; yet, most graphs have few automorphisms.

•

$g p h$ is monotonically increasing.

\xy(0,10)*\hbox{Graphs on $N$ vertices},(0,0)*[o]=<40pt>\hbox{G}*\frm{o},(5,0)% *\hbox{$\bullet$},(-3,-3)*\hbox{$\bullet$},(-4,2)*\hbox{$\bullet$};\qquad% \hookrightarrow\qquad\xy(0,10)*\hbox{Graphs on $N+1$ vertices},(0,0)*[o]=<40pt% >\hbox{G}*\frm{o},(5,0)*\hbox{$\bullet$},(-3,-3)*\hbox{$\bullet$},(-4,2)*\hbox% {$\bullet$},(10,0)*\hbox{$\bullet$};

References

1 Harary, Frank and Palmer, Edgar M. Graphical enumeration Academic Press, New York, 1973, pp. xiv+271, 05C30, MR MR0357214 (50 #9682)