After 32 years, Bondy and Murty have updated their original text, and the result is a far more comprehensive treatment of the subject, rich in both theory and applications. This is achieved not by merely adding a few chapters to the original text; the new edition is, indeed, a reworking of the original material, producing a work more than double in size, in deference to what the authors term “this flourishing discipline.”
There are twenty one chapters, elegantly laid out, with challenging exercises following the more straightforward ones in individual sections. Following the exercises for the last section in a given chapter, there is a comprehensive (sometimes several pages long) discussion of “Related Reading,” pointing the interested reader to more information about a topic that the authors hadn’t the room or scope to include in the text. Even better, the new edition includes copious illustrations, confirming an important fact often maddeningly neglected in many graph theory papers and texts: the material lends itself to illustration! Thirty pages of references are included, as well as eight pages of unsolved problems. Graph Theory is a subject particularly fertile in topics for undergraduate research. The authors intend the text for advanced undergraduates in mathematics as well as beginning graduate students in mathematics and computer science, but they have in fact produced something more valuable: an excellent resource for anyone pursuing research in Graph Theory.
What sets this particular text apart from others is the balance between theory and applications. One can find texts that do one or the other well, but rarely both. For example, the original edition presented a proof of Kuratowski’s Theorem on planar graphs (a graph is planar iff it contains no subdivision of K5 or K3,3) using a technique of Dirac and Schuster from 1954. In the new edition, they employ a proof of Thomassen from 1981, then go on to explain how the theorem gives rise to a polynomial time decision algorithm for planarity.
The book offers the best of both worlds. For instance, the chapter on matchings includes the statement and proof of Berge’s theorem relating matchings and augmenting paths. Then, in a later section of the same chapter, the augmenting path search algorithm is presented. It gives an instructor adopting the text an obvious flexibility in presentation, depending on the student audience.
Bondy and Murty propose that the turning point for Graph Theory was the 1976 “verification” of the Four-Color Theorem by Appel and Haken, coincidentally, the publication year of the first edition of their text. In the first edition, the Four Color “Conjecture” received a short mention in the chapter on planar graphs. In the new edition, the Four Color Theorem gets its own chapter (albeit the shortest in the whole text).
For anyone adopting this text, its strongest feature might be the blog, located at http://blogs.springer.com/bondyandmurty/. At this site, the up-to-the-minute errata are posted. For example, Lemma 21.27 is proven by induction in a way that, as one reader pointed out, would preclude multigraphs. The authors generally do not make a point to always distinguish between simple graphs and multigraphs (though maybe they should). They responded:
In the case of simple graphs, this difficulty does not arise. Nonetheless, the statement of the lemma is correct. We give here a modified proof which is valid for multigraphs.
One click of the mouse leads the reader to the modified proof.
If there can be any criticism of the text, it might be that the rich field of algebraic and matrix graph theory is not given as much treatment as this reviewer would like, but one supposes that they had to stop somewhere. In addition, they don’t always include the most accessible proof of a theorem. For example, the proof of Turán’s Theorem in the first edition was due to Erdős from 1970. In the new edition, they reach back to a 1949 proof by Zykov. However, the one by Boesch, Gross, Kazmierczak, Stiles, and Suffel, “On the extensions of Turán’s theorem” [Graph Theory Notes of New York, 2001], is far more accessible, particularly to undergraduates, for the triangle case. Once again, they had to stop somewhere.
John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.