# Pearls in Graph Theory: A Comprehensive Introduction

###### Nora Hartsfield and Gerhard Ringel
Publisher:
Dover Publications
Publication Date:
2003
Number of Pages:
272
Format:
Paperback
Price:
16.95
ISBN:
0486432327
Category:
Textbook
BLL Rating:

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Mark Hunacek
, on
09/17/2015
]

According to the authors, a “pearl…. could be a graph, theorem, proof, conjecture, or exercise that provokes thought, causes surprise, stimulates interest or inspires further research.” There are many of them in this book, but it would be incorrect to classify this book as merely a random collection of interesting results in graph theory. Instead, it is a systematic development of the subject, starting more or less from scratch, and (subject to some concerns about omitted topics, to be discussed below) might make an interesting text for an undergraduate (junior-level, perhaps) course in graph theory.

The book certainly has many attributes of a good text. Clear, detailed explanations, combined with an obvious enthusiasm on the part of the authors, make it enjoyable to read; there are lots of examples; and there is also a plentiful supply of well-chosen exercises, solutions to which are not available in the text (and also apparently not in any kind of instructor’s manual). This is a book that students should find stimulating and pleasant.

The authors begin with the definition of a graph and give a number of examples of them. (Although prior exposure to graph theory is not a prerequisite for this book, some prior background in proof-related courses is; mathematical induction, for example, is freely used early on.) The first few chapters discuss relatively standard topics: trees, Hamiltonian cycles and Eulerian circuits, the Havel-Hakimi theorem on graphical sequences, etc. The notion of graph colorings (edge and vertex) are introduced as early as chapter 2, and discussed in more detail in later chapters, including, of course, discussions of the Four Color theorem (and the easier Five Color theorem). The late Professor Ringel — he died in 2008, a few months shy of his 89th birthday — did a lot of work in the areas of colorings, planarity, and graphs on other surfaces, and these topics, not surprisingly, receive considerable emphasis in this text. Few if any other undergraduate texts cover topological graph theory in the kind of detail that this book does.

Other interesting topics, a number of which were new to me, are discussed throughout the book. There is a chapter on labeling graphs, where, for the first time, I learned about magic and antimagic graphs and graceful trees. A chapter on extremal graph theory introduces the concept of a cage, as well as providing a statement and proof of Turán’s theorem and an introduction to Ramsey theory.

Other chapters cover graph algorithms, counting problems, including the problem of counting spanning trees in certain kinds of graphs. For the complete graph on $n$ vertices, the answer is $n^{n-2}$, a famous result of Cayley). There is a discussion of an interesting open problem called the Oberwolfach Problem, posed by Ringel after observing the dining at the famous mathematics institute in Germany: is it possible to seat an odd number $m$ of mathematicians, at $n$ round tables, for $(m-1)/2$ meals, so that every mathematician sits next to everybody else exactly once? (This can, of course, be given a graph-theoretic formulation.) In addition, in one (and only one) section, the authors even consider infinite graphs.

There are also, however, a number of topics that aren’t discussed in this text, and perhaps should have been. Most problematic, I thought, was the complete absence of any discussion of matrix methods in graph theory. Even the simplest object — the adjacency matrix of a graph — is not mentioned at all. The exclusion of matrices from this book is troublesome, I think, for several reasons: first, I believe it is advisable on general principles to point out to students, whenever reasonably possible, that different areas of mathematics can have a nice interplay with one another. Second, the connections between graph theory and matrices are interesting and the subject of current active research, yet a considerable amount of this subject is within the grasp of undergraduates. (In this connection, I cannot resist mentioning Richard Brualdi’s book The Mutually Beneficial Relationship of Graphs and Matrices. Based on a week-long series of lectures at Iowa State University that I had the privilege of attending, and accurately described in a review in this column as a “delightful” book that “could be used as a supplemental course book in an upper level undergraduate course….”, this book discusses a number of connections between graphs and matrices in detail.)

There are other omissions as well. Many undergraduate books (see, e.g., Chartrand and Zhang’s Introduction to Graph Theory) have a chapter on connected graphs in which are discussed such things as cut vertices, blocks and Menger’s theorem; these are not mentioned in the book under review, although the related concept of bridges is. (And while I’m on the subject of connected graphs, let me also record my mild unhappiness with the authors’ definition of a connected component; as defined on page 45: only disconnected graphs have components.) The subject of matchings is also discussed here, but one of my favorite theorems in that area, Hall’s theorem, is not.

There are also some results that are mentioned, but not proved. Vizing’s theorem is an example of this, and two graph algorithms discussed in chapter 7 (Kruskal’s algorithm and the Hungarian algorithm), are not proved to work. The five-color theorem is not proved for all planar maps (as in the aforementioned book by Chartrand and Zhang, or in Trudeau’s Introduction to Graph Theory), but only for certain kinds of them.

Of course, there is no firm consensus as to exactly what topics should be covered in a beginning course in graph theory, and the comments above reflect my own personal tastes and biases. Undoubtedly there are many instructors of graph theory courses who would, for example, much prefer to talk about topological graph theory than the applicability of matrix theory to the subject. Such instructors should definitely consider this as a possible text for an undergraduate course. And even those people, like me, who really feel the loss of some of the topics listed above will want to have this book available as a supplemental reference. The authors’ stated goal (“maximizing the pleasure for both the teacher and the student”) has been achieved.

Mark Hunacek ([email protected]) teaches mathematics at Iowa State University.

 Foreword 1. Basic Graph Theory 2. Colorings of Graphs 3. Circuits and Cycles 4. Extremal Problems 5. Counting 6. Labeling Graphs 7. Applications and Algorithms 8. Drawings of Graphs 9. Measurements of Closeness to Planarity 10. Graphs on Surfaces References. Index.