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)/2and 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