You are here

The Fascinating World of Graph Theory

Arthur Benjamin, Gary Chartrand, and Ping Zhang
Princeton University Press
Publication Date: 
Number of Pages: 
BLL Rating: 

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

[Reviewed by
Mark Hunacek
, on

The authors of this book are all experienced expositors in the area of discrete mathematics. Benjamin is the co-author of Proofs That Really Count, and is also the lecturer in a number of videos in the Great Courses series; Chartrand and Zhang have written a number of other graph theory textbooks, including Introduction to Graph Theory. Here they have set out to make graph theory not only accessible to people with a limited mathematics background, but also to make it interesting. They have — by virtue of very clear writing, combined with a greater-than-usual emphasis on the historical and personal side of the subject — succeeded admirably.

The contents of this book track a traditional undergraduate course in graph theory. Graphs are defined in the first chapter, after which are discussed the usual topics, including isomorphism, connectivity, trees, Eulerian and Hamiltonian graphs, planarity, and colorings.

Although these topics are standard, the method of presentation in this text is not. The authors take pains to motivate all these topics with interesting applications and discussion of historical problems. Before the formal definition of a graph is given (on page 18), for example, the text has already discussed the concept from a more intuitive point of view and has presented more than half a dozen problems, some of which (for example, the Königsberg Bridge problem or the three utilities problem) have considerable historical significance and are responsible for the development of some of the theory in this subject.

This emphasis on motivation through applications and problems pervades the entire text. The human element is not neglected, either. The famous names of graph theory are discussed; both biographical sketches and historical anecdotes are provided. For example, the chapter on graph coloring, which (not surprisingly) focuses on the four-color problem, begins with a lengthy history of that problem, covering about twelve pages of text, discussing a number of people who, over the years, have been involved with it.

A natural question that arises is whether this book is intended as a text for an undergraduate course in graph theory or as a “general math” book for a lay audience. Indeed, it was primarily curiosity about this question that prompted me to request this book to review; the available descriptions didn’t really answer it.

Having now seen the book, I have to confess that I’m still not completely sure what the answer is. It has attributes of both the latter and former type. For example, there are definitely some features presented here that are typically found in an undergraduate text: definitions are generally precise rather than vague and intuitive as one might expect in a text for general audiences; mathematical notation is used; theorems are labeled as such and sometimes accompanied by proofs; and exercises (some of them calling for proofs) appear at the end of the book, grouped according to chapter.

For these reasons, I doubt that this book will find much use among completely untrained readers. This seems intentional: although the mathematical prerequisites for reading this book have been kept to a minimum, it appears the authors are assuming at least some mathematical training on the part of the audience. The preface, for example, contains the statement that the areas of mathematics “with which you are probably most familiar include algebra, geometry, trigonometry and calculus.”

On the other hand, some instructors may feel that the book is too elementary for a typical junior level course in graph theory for math majors. The proofs (and in some cases even the statements) of a number of theorems that appear in other graph theory texts are omitted, for example, and the exposition is somewhat less terse and more conversational than what is often found in upper-level texts. There is more of an emphasis on calling attention to interesting problems than in systematically developing the theory from scratch. Also, the fact that the exercises appear at the end of the book, rather than at the end of each chapter, may suggest that the authors wanted them to be easily omitted; perhaps they were afraid of scaring away non-student readers.

Perhaps the best use of the book would be as a text for a lower-level course in graph theory, or as a supplementary reference for an instructor looking for additional motivational materials for an upper-level course. It would also be very interesting, I think, to see if this book could be used successfully as a text for an honors-level senior high school course in discrete mathematics, or as a freshman honors seminar at the college level, as a way of making clear to students that there is more to mathematics than simply factoring quadratic equations or mechanically setting derivatives equal to zero. I believe the answer is a clear “yes”.

Mark Hunacek ( teaches mathematics at Iowa State University.

Preface vii
Prologue xiii
1 Introducing Graphs 1
2 Classifying Graphs 22
3 Analyzing Distance 45
4 Constructing Trees 67
5 Traversing Graphs 91
6 Encircling Graphs 108
7 Factoring Graphs 125
8 Decomposing Graphs 143
9 Orienting Graphs 164
10 Drawing Graphs 183
11 Coloring Graphs 206
12 Synchronizing Graphs 226
Epilogue Graph Theory: A Look Back—The Road Ahead 251
Exercises 255
Selected References 309
Index of Names 317
Index of Mathematical Terms 319