Enumerating the number of graphs with n verticies and p lines.

Let binom( n m ) denote the binomial coefficent

          binom( n m )  :=  n!/(m! (n-m)!)

Consider a set of n verticies, and the undirected graphs that can be constructed with them. The number of possible lines connecting them (also the number of lines in the complete n-vertex graph) is the number of ways of pairing the verticies, where the order of the pairing doesn't count:

          binom( n 2 )  =  n(n-1)/2

Then the number p, of lines in an n-vertex graph has values

          0  <=  p  <=  n(n-1)/2

and the number of p-line n-vertex graphs is

          binom( binom( n 2 ) p )

Summing over all values of p, gives the total number of n-vertex graphs

          SUM(p) binom( binom( n 2 ) p )  =  2^binom( n 2 )

The counting is for graphs in general and is not dependent on the assumption of isometricity.

Top of Page
Home Page
Physics Page

Email me, Bill Hammel at

The URL for this document is:
Created: 1997
Last Updated: May 28, 2000