You are here

Graph Theory

Reinhard Diestel
Springer Verlag
Publication Date: 
Number of Pages: 
Graduate Texts in Mathematics
BLL Rating: 


[Reviewed by
Michael Berg
, on

Graph theory is one of those subjects I wish I knew a lot about, but don’t. In my undergraduate days I was at best a fellow traveler alongside bona fide combinatorists, Ramsey theorists, and graph theorists, but I was never a true apprentice of any one of them (number fields exerted too strong a pull). However, frequent exposure did have its effects and I came to understand that there are a host of beautiful results in graph theory, often remarkably easy to state and even illustrate, but ever so difficult to prove.

Graph theory shares this property also with combinatorics as well as with elementary number theory and it has a lot of overlap with these fields, of course — so much so that it is sometimes difficult to say where one discipline ends and the other begins. Admittedly, drawing such borders is perhaps a synthetic and misguided exercise, but one does want to know the scope of one’s subject. Graph Theory aims to answer this question at least at the level of a beginner in the field: there is a well-defined core of material every self-respecting graph theorist should know, and a useful graduate-level textbook goes a bit further by introducing what should (or might) loom on the horizon as research in the field progresses.

In fact, in the Preface to the book, Reinhard Diestel poses the explicit question: “what are, today, the essential areas, methods and results that should form the centre of an introductory graph theory course aiming to equip its audience for the most likely developments ahead?,” and the book’s table of contents delineates his answer: matching, covering and packing, connectivity, planar graphs, coloring graphs, flows, extremal graphs, infinite graphs, Ramsey theory for graphs (straddling two areas and erasing part of a border?), Hamilton cycles, random graphs, and, finally, minors, trees and well-quasi-ordering (how’s that for peaking the interest of a nosy would-be reader?). So there it is: if you want to be a graph theorist, learn all this stuff well — and, to be sure, this is a superb place to learn it.

Graph Theory  is a very well-written book, now in its third edition and the recipient of the according evolutionary benefits. It succeeds dramatically in its aims, which Diestel gives as “[providing] a reliable first introduction to graph theory that can be used for personal study or as a course text, [and] a graduate text that offers some depth in selected areas.” The margins are filled with cryptic but useful references and indicators of appearances of important players (still leaving more than enough room for the enthusiastic reader to do battle with the text with his own marginalia); the theorems are presented elegantly and concisely (often replete with attribution: Erdös’ name abounds, of course), as are their proofs; there are many exercises, with good hints; and the chapters’ end notes are a model of scholarship and a pleasure to read. Even the pictures and drawings are nice. This is a hell of a good book!

Unlike, say, algebraic geometry, graph theory is one of those marvelous disciplines which are very beautiful and serious but at the same time get off the ground very quickly. An able and energetic fledgling would be safely pointed in this direction, and should be given this book as standard issue.


The Basics
Matching, Covering and Packing
Planar Graphs
External Graph Theory
Infinite Graphs
Ramsey Theory for Graphs
Hamilton Cycles
Random Graphs
Minors, Trees, and WQO
Appendix A: Infinite Sets
Appendix B: Surfaces.