The number of connected sparsely edged graphs

Author:
Publisher website
Google Scholar
Abstract
An (n, q) graph has n labeled points, q edges, and no loops or multiple edges. The number of connected (n, q) graphs is f(n, q). Cayley proved that f(n, n‐1) = nn−2 and Renyi found a formula for f(n, n). Here I develop two methods to calculate the exponential generating function of f(n, n + k) for particular k and so to find a formula for f(n, n + k) for general n. The first method is a recurrent one with respect to k and is well adapted for machine computation, but does not itself provide a proof that it can be continued indefinitely. The second (reduction) method is much less efficient and is indeed impracticable for k greater than 2 or 3, but it supplies the missing proof that the generating function is of a particular form and so that the first method can be continued for all k, subject only to the capacity of the machine.

This publication has 2 references indexed in Scilit: