Analytic Graph Theory
Jonathan L. Gross, Jay Yellen, Mark D. Anderson · 2023
Several areas of graph theory are concerned with the likelihood or certainty of the presence in a graph of various subgraphs or, more generally, of graph properties that emerge as the number of vertices and/or the number of edges increases. Collectively they are grouped as analytic graph theory. The foundational results in analytic graph theory were obtained decades ago, and there has been extensive subsequent development. This chapter focuses on the basic results whose proofs are the most readily accessible and illuminating. A random graph is a graph in which the number of vertices is specified and the adjacencies between vertices are determined in some random way. The theory of random graphs uses probabilistic methods to establish the existence of certain kinds of graphs and to determine some properties of “almost all” graphs in various families.