How many graphs are there?
The number of isomorphisms from a graph to a graph is equal to the number of automorphisms of (or ). Therefore the total number of isomorphisms between two graphs is no more than – the total number of permutations of the vertices of . Therefore the total number of non-isomorphic simple graphs on vertices is at least .
The gap between the bounds is superexponential in : that is: . However logarithmically the estimate is tight:
is closer to the lower bound; yet, most graphs have few automorphisms.
is monotonically increasing.
- 1 Harary, Frank and Palmer, Edgar M. Graphical enumeration Academic Press, New York, 1973, pp. xiv+271, 05C30, MR MR0357214 (50 #9682)
|Date of creation||2013-03-22 15:50:07|
|Last modified on||2013-03-22 15:50:07|
|Last modified by||Algeboy (12884)|