Around twenty years ago, the late Frank Harary’s Graph Theory was the standard for all texts in the discipline. Well-written, inclusive, and with challenging exercises, this book was the one people in the field would reference in their research papers (“For all Graph Theoretic terminology not included here, we refer the reader to Harary”). While Harary’s text remains excellent, the text of choice among Graph Theorists seems to have become Douglas West’s Introduction to Graph Theory. With so many competing texts out there, why is West’s book becoming the standard?
For one thing, the book is very well written, and contains material that has become a part of the subject as it has evolved. For example, he includes a significant section on matrices associated with graphs, and a proof of Kirchhoff’s Matrix-Tree Theorem, which is covered in most competing texts. He even includes an alternate proof of the result at the book’s website (http://www.math.uiuc.edu/~west/igt/), which also includes errata and a reader poll on terminology for a promised third edition.
This book is an excellent reference for Graph Theory. The section on Hamiltonian Cycles is quite good, and the chapter on matchings and factors, is, well, unmatched. It includes comprehensive coverage of Hall’s Theorem and its consequences, as well as an optional section on dominating sets that leads to more challenging investigations. Network flows, colorings and connectivity are also given a full treatment. The final chapter, Chapter 8, covers some advanced topics that could be pursued further by graduate students, such as perfect graphs, matroids, and extremal graph theory topics such as Ramsey Theory.
West includes a particular encoding of his exercises, of which there are a rich collection. Exercises marked “(+) “ or “(–)” are, respectively, more difficult or less difficult than unmarked problems, while “(!)” problems are “especially valuable, instructive, or entertaining.” He does caution that “(+)” problems should not be assigned as homework in a typical undergraduate course. Finally, “(*)” problems are those that are from material in so-called “optional” sections of the text.
West includes a number of appendices, covering such topics as background material on mathematical proofs, computational complexity of algorithms, a glossary of terms, and copious references. In short, this is an excellent text for advanced undergraduate or beginning graduate students, and their professors.
John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ
1. Fundamental Concepts.
2. Trees and Distance.
3. Matchings and Factors.
4. Connectivity and Paths.
5. Coloring of Graphs.
6. Planar Graphs.
7. Edges and Cycles.
8. Additional Topics (Optional).
Appendix A: Mathematical Background.
Appendix B: Optimization and Complexity.
Appendix C: Hints for Selected Exercises.
Appendix D: Glossary of Terms.
Appendix E: Supplemental Reading.
Appendix F: References.