This is a long and technical paper on graphical enumeration for connected graphs (and multigraphs) with n vertices and n+k edges. Let G_n,k denote such a graph. The technique used is that of formal exponential generating series. The main contribution of the paper is a proof that almost all connected G_n,k for n,k → ∞ and k = o(n^1/3) are triangle-free. In fact, Corollary 32 gives more detailed information on the number of such graphs. The proof makes use of a long chain of lemmas, chiefly devoted to obtaining bounds on coefficients of various generating formal series, and making heavy use of the fundamental fact, first demonstrated in detail by E.M. Wright, that many exponential generating series used in graphical enumeration are expressible as rational series in the tree enumerating series. The enumeration information is extracted from the leading terms of series of this type.

The lemmas use three kinds of arguments: upper or lower bounding of coefficients; surgery on graphs; and analytic estimation, namely, the saddle point method. The surgery on graphs argument consists of identifying small subgraph structures and blowing up vertices to trees, or contracting trees to vertices. These surgeries establish connections to integer partitioning. The ultimate object of the paper is to obtain enumerative asymptotics for connected graphs with k = o(n^1/3) that exclude any given family of subgraphs. However, the arguments are already so intricate for triangle exclusion that some form of mechanization through a computer algebra system would be needed for any serious extension of the results. Recently, Flajolet, Salvy, and Schaeffer announced a purely analytic representation for the generating series for G_n,k, n,k arbitrary. This means, at least, that many of the coefficient-by-coefficient bounding arguments needed when using formal series may be avoidable.