Counting Connected Graphs

-
Joel Spencer, New York University

 Let C(n,k) be the number of labelled connected graphs with n vertices and n-1+k edges.  For k=0 (trees) we have Cayley's Formula.  We examine the asymptotics of C(n,k).  There are several approaches involving supercritical dominant components in random graphs, local limit laws, Brownian excursions, Parking functions and other topics.