Date on Master's Thesis/Doctoral Dissertation


Document Type

Master's Thesis

Degree Name




Committee Chair

Davitt, Richard M.


Graph theory--History


The field of graph theory has been indubitably influenced by the study of planar graphs. This thesis, consisting of five chapters, is a historical account of the origins and development of concepts pertaining to planar graphs and their applications. The first chapter serves as an introduction to the history of graph theory, including early studies of graph theory tools such as paths, circuits, and trees. The second chapter pertains to the relationship between polyhedra and planar graphs, specifically the result of Euler concerning the number of vertices, edges, and faces of a polyhedron. Counterexamples and generalizations of Euler's formula are also discussed. Chapter III describes the background in recreational mathematics of the graphs of K5 and K3,3 and their importance to the first characterization of planar graphs by Kuratowski. Further characterizations of planar graphs by Whitney, Wagner, and MacLane are also addressed. The focus of Chapter IV is the history and eventual "proof" of the four-color theorem, although it also includes a discussion of generalizations involving coloring maps on surfaces of higher genus. The final chapter gives a number of measurements of a graph's closeness to planarity, including the concepts of crossing number, thickness, splitting number, and coarseness. The chapter conclused with a discussion of two other coloring problems - Heawood's empire problem and Ringel's earth-moon problem.