# 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.
• ($\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.

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