ABSTRACT
Graph theory might better be named network theory. It is the study of structures that model such things as computer networks and transportation networks. After providing some motivating examples, the formal definitions, and the basic terminology of graphs, this chapter presents several fundamental graphs. The introduction to graph theory begins with the Konigsberg Bridge Problem. Matrices are then studied and seen to be more than merely a storage device for graph adjacencies. The chapter discusses when two graphs should be considered equivalent and how to justify when they are not. Graph operations reminiscent of set operations are also studied. The chapter also considers variations that result from assigning a particular direction to each edge. This leads to a discussion of Markov chains. Because graphs can be used to model many kinds of real-world problems, applications are explored. The numbers of vertices and edges provide very simple examples of graph invariants.
