Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The fascinating world of graph theory
Benjamin A., Chartrand G., Zhang P., Princeton University Press, Princeton, NJ, 2015. 344 pp.  Type: Book (978-0-691163-81-9)
Date Reviewed: Jul 27 2015

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

Reviewer:  Paul Cull Review #: CR143655 (1510-0863)
1) Deo, N. Graph theory with applications to engineering and computer science. Prentice Hall, Englewood Cliffs, NJ, 1974.
2) Even, S. Graph algorithms. Computer Science Press, Potomac, MD, 1979.
Bookmark and Share
  Reviewer Selected
Editor Recommended
Graph Theory (G.2.2 )
Introductory And Survey (A.1 )
Would you recommend this review?
Other reviews under "Graph Theory": Date
Fuzzy graph theory
Mathew S., Mordeson J., Malik D.,  Springer International Publishing, Cham, Switzerland, 2018. 320 pp. Type: Book (978-3-319714-06-6)
Aug 24 2018
New infinite family of regular edge-isoperimetric graphs
Bezrukov S., Bulatovic P., Kuzmanovski N.  Theoretical Computer Science 721(C): 42-53, 2018. Type: Article
Aug 10 2018
Large induced forests in graphs
Shi L., Xu H.  Journal of Graph Theory 85(4): 759-779, 2017. Type: Article
Jul 30 2018

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2018 ThinkLoud, Inc.
Terms of Use
| Privacy Policy