ABSTRACT
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
6.1 Introduction Many references to date on the enumeration of graphs deal with unlabeled graphs, like the monographs of Harary and Palmer [32] and Po´lya and Read [50]. The main tool there is the cycle index polynomial and the goal is to obtain exact expressions for the number of graphs of a given kind, like trees or connected graphs. Our emphasis in this survey is instead on labeled graphs. One reason is that in many interesting cases the number of unlabeled graphs with n vertices is asymptotically the number of labeled graphs divided by n!, the number of possible labelings. This is not always so, as in the case of trees, since a random tree has almost surely exponentially many automorphisms.
