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.
Email me, Bill Hammel at