enumerating graphs

How many graphs are there?

Proposition 1.

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

  • ()

    Every simple graph on N vertices can be encoded by a N×N symmetric matrixMathworldPlanetmath with all entries from {0,1} and with 0’s on the diagonalMathworldPlanetmath. Therefore the information can be encoded by strictly upper triangular N×N matrices over {0,1}. This gives 2(N2) possibilities.

  • ()

    The number of isomorphismsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 permutationsMathworldPlanetmath of the N vertices of G. Therefore the total number of non-isomorphic simple graphs on N vertices is at least 2(N2)/N!.

  • The gap between the bounds is superexponential in N: that is: O(2(N2)). However logarithmically the estimate is tight:

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

  • gph is monotonically increasing.

    {xy}(0,10)*Graphs on N vertices,(0,0)*[o]=<40pt>G*\frmo,(5,0)*,(-3,-3)*,(-4,2)*;  {xy}(0,10)*Graphs on N+1 vertices,(0,0)*[o]=<40pt>G*\frmo,(5,0)*,(-3,-3)*,(-4,2)*,(10,0)*;


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