ABSTRACT
Graph theory is a branch of discrete mathematics that studies networks composed of a number of sites (vertices) linked together by connecting arcs (edges). This chapter studies some enumeration problems that arise in graph theory. We begin by defining fundamental graph-theoretic concepts such as walks, paths, cycles, vertex degrees, connectivity, forests, and trees. This will lead to a discussion of various enumeration problems involving different kinds of trees. Aided by ideas from matrix theory, we will count walks in a graph, spanning trees of a graph, and Eulerian tours. We also investigate the chromatic polynomial of a graph, which counts the number of ways of coloring the vertices such that no two vertices joined by an edge receive the same color.
