What could be simpler than graph theory? While it may be just a bunch of dots connected by some lines, graph theory is also very general because it encompasses all two-place relations. Because of this simplicity and generality, graph theory is an ideal vehicle to expose people to real mathematics (beyond usual arithmetic) while appealing to their intuition and sense of fun.

The authors have produced a book that falls between a popularization and a text. They have concocted a nice mix of storied problems, historic vignettes, and theorems that make for long stretches of easy reading with occasional slow-downs to ponder proofs.

The book opens with a number of classic problems that are given as stories and then represented as graphs; the problems are then restated as graph theory problems.

The remaining 11 chapters, each of about 20 pages, cover portions of graph theory. For example, there are chapters on trees, distances, traversals, classification, encircling, factoring and matching, decomposition, orienting, drawing and planar graphs, coloring, and even Ramsey theory. The stories of the people who solved the problems are included along with the discussion of the problem. Solutions are given to many classical problems including what may be the oldest solution to the Knight’s tour. There are also some more modern problems including the solution to Instant Insanity via graph factoring.

The book contains many diagrams and is notably free from typographical errors. I caught a few: Erno Rubick is given as “Emo Rubick,” and Figure 9.8 is missing one arrowhead. The history seems to be correct and is more detailed than in other books, but the authors’ version of the Courant/Robbins story differs a little from the stories I’ve heard.

Computer science instructors may be disappointed to see so little discussion of algorithms. Complexity is hinted at, but NP-completeness is, wisely, not mentioned. Such instructors might prefer the classic books by Deo [1] and Even [2].

The main body of the book is about 250 pages, and this is followed by 50 pages of exercises. There is clearly enough here for a one-term undergraduate course. I enjoyed reading this book, and I believe that other teachers will similarly enjoy it and find some tidbits to use in their courses. Finally, this book is easy enough to read that bright high school students will also find it fascinating.

More reviews about this item: Amazon, Goodreads