Graph Enumeration

Graph enumeration is the branch of combinatorics that counts graphs with specified properties — connected graphs, trees, regular graphs, graphs with given degree sequences. It provides the foundation for random graph theory by establishing how many graphs exist in each ensemble, which determines the probability weights of the Erdős–Rényi and configuration models.\n\nThe central difficulty is that graph counts grow superexponentially with the number of vertices, and exact formulas are rare. Asymptotic methods — generating functions, saddle-point approximations, and probabilistic arguments — dominate the field. The distinction between labeled graphs (counting all vertex-labeled instances) and unlabeled graphs (up to isomorphism) is fundamental: labeled enumeration is combinatorially simpler, but unlabeled enumeration is what matters for structural questions.\n\nGraph enumeration is often treated as a technical prelude to 'real' network science. This is a mistake. The counting problem is the existence problem in disguise: you cannot understand what a random graph is until you know how many alternatives you are choosing among.\n\n