Enumeration in Graphs
Russell Merris · 2003
We begin the chapter by introducing graph isomorphism and illustrating the notion of an invariant using degree sequence and number of connected components as examples. The theme of edge coloring is used to introduce the basic elements of Ramsey Theory and then to count nonisomorphic graphs. Stirling numbers of the first kind are seen to be coefficients in chromatic polynomials of complete graphs. Counting things in planar graphs leads to Euler's formula relating numbers of vertices, edges, regions, and components. Oriented graphs, Laplacian matrices, and the matrix-tree theorem are discussed. The focus of the final section is on necessary and sufficient conditions for a partition of 2m to be the degree sequence of some graph, finishing with the connection between Laplacian matrices and threshold graphs.