Pearls in Graph Theory: A Comprehensive Introduction is an undergraduate-level textbook on graph theory by Nora Hartsfield and Gerhard Ringel. It was published in 1990 by Academic Press[1][2][3] with a revised edition in 1994[4] and a paperback reprint of the revised edition by Dover Books in 2003.[5] The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.[5]
The "pearls" of the title include theorems, proofs, problems, and examples in graph theory. The book has ten chapters; after an introductory chapter on basic definitions, the remaining chapters material on graph coloring; Hamiltonian cycles and Euler tours; extremal graph theory; subgraph counting problems including connections to permutations, derangements, and Cayley's formula; graph labelings; planar graphs, the four color theorem, and the circle packing theorem; near-planar graphs; and graph embedding on topological surfaces.[4][5]
The book also includes several unsolved problems such as the Oberwolfach problem on covering complete graphs by cycles, the characterization of magic graphs, and Ringel's Earth–Moon problem on coloring biplanar graphs.[3]
Despite its subtitle "A comprehensive introduction", the book is short and its selection of topics reflects author Ringel's personal interests.[1][5]. Important topics in graph theory that are not covered[1][4]include the symmetries of graphs, cliques, connections between graphs and linear algebra including adjacency matrices, algebraic graph theory and spectral graph theory, connectivity of a graph (or even biconnected components), Hall's marriage theorem, line graphs, interval graphs, and the theory of tournaments. There is also only one chapter of coverage on algorithms and real-world applications of graph theory.[1][4][5] Also, the book omits "difficult or long proofs".[2][5]
The book is written as a lower-level undergraduate textbook and recommends that students using it have previously taken a course in discrete mathematics. Nevertheless, it can be read and understood by students with only a high school background in mathematics. Reviewer L. W. Beineke writes that the variety of levels of the exercises is one of the strengths of the book,[4] and reviewer John S. Maybee writes that they are "extensive" and provide interesting connections to additional topics;[1] however, reviewer J. Sedláček criticizes them as "routine".[2]
Although several reviewers complained about the book's spotty or missing coverage of important topics,[1][4][5] reviewer Joan Hutchinson praised its choice of topics as "refreshingly different" and noted that, among many previous texts on graph theory, none had as much depth of coverage of topological graph theory.[3] Other reviewer complaints include a misattributed example,[2] a bad definition of the components of a graph that failed to apply to graphs with one component,[5] and a proof of the five-color theorem that only applies to special planar maps instead of all planar graphs.[3]
Despite these complaints, Beineke writes that, as an undergraduate text, "this book has much to offer".[4] Maybee writes that the book was "a joy to read", provided better depth of coverage on some topics than previous graph theory texts, and would be helpful reading for "many graph theorists".[1] Hutchinson praises it as providing "a splendid, enticingly elementary yet comprehensive introduction to topological graph theory".[3]