Reinhard Diestel
Graph Theory
Review from SIAM Review
This text presents an up-to-date, theoretical treatment of the
basic concepts of graph theory at a level that is appropriate
for beginning graduate students. The author's purpose is to provide
his view of the areas of graph theory that are important for current
research because of either recent activity or a perceived potential
for more progress. The book is an answer to the question raised
in its preface: "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?"
The author is the most recent recipient of the Hall Medal, awarded
by the Institute of Combinatorics and Its Applications to outstanding
researchers in midcareer. Given his active participation in several
areas of graph theory, he is qualified to take on this ambitious
task. The result is a concise, clear, and theoretical presentation
that covers all of the principal areas of modern graph theory,
while touching on a variety of subsidiary areas.
The reader who is interested in applications or algorithms will
be disappointed, for the author is very clear that this is a pure
mathematics text. However, for those with some previous exposure
to graphs, perhaps through their use in computer science or a
more intuitive course of study, this text is an excellent vehicle
for becoming familiar with a more formal approach to graph theory.
The book presumes a level of mathematical maturity that is about
that of a beginning graduate student in mathematics, and these
students are the book's most natural audience. A thorough study
of this text would provide the aspiring graph theorist with both
an in-depth survey of the major areas of the discipline and extensive
practice in the techniques and methods of arguments that are more
formal and structured than those seen at the undergraduate level.
But it is not a good choice for the reader who has little or no
exposure to graph theory; a full appreciation will require some
experience with the subject at a less rigorous level.
The book contains many excellent, detailed figures illustrating
the constructions used in proofs. Each chapter begins with a few
paragraphs that describe, in non-technical terms, how that chapter's
subject fits in with the rest of the book and the discipline.
Each chapter concludes with a page's worth of notes that describe
how that chapter's theorems fit into the development, and that
give pointers to articles and monographs for the interested reader
to pursue further study. Besides the book's overall economical
and clear presentation, these introductory and concluding sections
of each chapter are its strongest feature. The author credits
a course taken from Béla Bollobás for much of his
inspiration, since it was notes from this course that evolved
into Bollobás book Graph Theory - An Introductory Course.
The reader familiar with this earlier book will notice its beneficial
influence here. (Coincidentally, Bollobás's book has undergone
a major revision; a review of the revision follows this review.)
Each theorem contains a marginal note with a list of the previous
theorems it employs and the upcoming theorems that will depend
on it. This is an especially nice feature, particularly for an
instructor planning to cover only a subset of the book. However,
the margins are also littered with instances of notation or terms
at the locations where they are defined in the text. Often these
definitions have a limited lifetime, especially if they are used
in a short proof. For example, in one proof four symbols are defined
in the space of three lines, with each symbol being displayed
in the margin. The proof runs for three more lines, making references
to each of these symbols, and then the proof ends. The utility
of such a device is debatable. When a single page contains as
many as 14 such notes, this reader found it very distracting.
The defined terms appear in the index, so it is not necessary
that they appear in the margin.
Each chapter contains, on average, about 20 exercises, with the
easy and difficult ones tagged as such. For the budget-minded,
the book is available in a softcover version.
Chapter titles include: "Matching," "Connectivity,"
"Planar Graphs," "Colouring," "Flows,"
"Substructures in Dense Graphs," "Substructures
in Sparse Graphs," "Ramsey Theory for Graphs,"
"Hamilton Cycles," "Random Graphs," "Minors,
Trees and Well-Quasi-Ordering." While experienced researchers
might find some of their favorite topics missing, it would be
hard to argue that the choice of topics does not provide an answer
to the author's question in the preface.
This text gives the reader a concise, economical discussion of
the important areas of current research, while also taking care
to place the results in context; it is more than a compendium
of theorems and proofs. It would be an excellent choice as a textbook
for a second course in graph theory for graduate students in mathematics.
It will also be welcomed by more advanced readers who wish to
quickly obtain an in-depth background in a specific area of research,
and who will benefit from the suggestions for further reading
that are provided by the chapter notes.
Robert A. Beezer
University of Puget Sound
List of reviews
Return to home page