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
bhammel@graham.main.nc.us
READ WARNING BEFORE SENDING E-MAIL

The URL for this document is:
http://graham.main.nc.us/~bhammel/PHYS/grafcnt.html
Created: 1997
Last Updated: May 28, 2000