# enumerating graphs

How many graphs are there?

###### Proposition 1.

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}}.$
###### Proof.

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

• $gph$ 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)
Title enumerating graphs EnumeratingGraphs 2013-03-22 15:50:07 2013-03-22 15:50:07 Algeboy (12884) Algeboy (12884) 6 Algeboy (12884) Theorem msc 05C30 EnumeratingGroups