Reinhard Diestel
Graph Theory
Review from Optima
Have you heard of Szemerédi's regularity lemma? If you have been
in touch with graph theory at least a little, the answer is almost surely
yes. How about its proof? In case you were so far too afraid to go through
the details and understand the basic ideas of this far-reaching result,
the book Graph Theory by R. Diestel will prove an excellent guide.
One of the main strengths of this book is making deep and difficult results
of graph theory acessible.
Actually, the goal of this book is (at least) twofold: First, to give a
solid introduction to basic notions and provide the standard material of
graph theory, such as the matching theorems of König, Hall, Tutte,
Petersen, the theorems of Dilworth and Menger on paths and chains, Kuratowski's
characterization of planar graphs, coloring theorems of Brooks and Vizing,
etc. But already the introductory chapters include results which have not
yet appeared in textbooks: Mader's theorem (1.4.2) on the existence of k-connected
subgraphs of a sufficiently dense graph, Tutte's characterization of 3-connected
graphs. It is also refreshing to see the proof of Mader's theorem (3.6.1)
on the existence of large topological complete graph as a minor in a dense
graph, or of the pretty theorem of Jung and of Larman and Mani (3.6.2) stating
the existence of k disjoint paths between any set of k
pairs of nodes in a sufficiently highly connected graph.
The main novelty of this book, however, is that a great number of difficult
and deep theorems, along with their full proofs, are exhibited. These include
some older results like Szemerédi's above-mentioned regularity lemma,
or Fleischner's theorem (10.3.1) on the Hamiltonicity of the square of a
graph, with a full proof of over seven pages. A fundamental result (Theorem
9.3.1) (due to three groups of authors around the beginning of the '70s)
from induced Ramsey theory is also completely proved (four pages). The classical
results on algebraic flows, including Tutte's investigations and Seymour's
6-flow theorem, are fully covered as well. Not only Lovász's perfect
graph theorem (5.5.3), stating the perfectness of the complement of perfect
graphs, is discussed, but his second, significantly deeper characterization
of perfect graphs, as well (Theorem 5.5.5). (Naturally, not every fundamental
result of graph theory could be included with its proof; but perhaps --
if the reviewer may make a suggestion -- the author may find a way in the
next edition to exhibit a proof of Mader's beautiful theorem (3.4.1) on
the maximum number of independent H-paths.)
Beyond these classics, recent or even brand-new results are also discussed.
For example, Galvin's charming list-colouring theorem (5.4.4) has appeared
in 1995, or Thomassen's pearl on 5-choosability of planar graphs in 1994.
An even more recent, very difficult result (Theorem 8.1.1), due to Komlós
and Szemerédi and to Bollobás and Thomason, state that every
graph with average degree at least cr2 contains Kr
as a topological minor. The paper of Komlós and Szemerédi
appeared in 1996 while the work of Bollobás and Szemerédi
has appeared only this year. Isn't it nice that a proof (of more than five
pages) is already accessible in Diestel's book?
A grand undertaking of the past 15 years has been the proof of the so-called
minor theorem (what a contradiction between name and significance!) It reads:
in every infinite set of finite graphs there are two such that one is
the minor of the other. The supporting theory of tree-decompositions,
well-quasi-orderings, minors has mainly been developed by N. Robertson and
P. Seymour. The complete proof of the minor theorem is over 500 pages, so
not surprisingly this is excluded here, but Chapter 12 on Minors, Trees
and WQO offers an excellent overview of the framework of the proof along
with its far-reaching consequences.
The book includes 12 chapters: (1) The Basics, (2) Matching, (3) Connectivity,
(4) Planar Graphs, (5) Colouring, (6) Flows, (7) Substructures in Dense
Graphs, (8) Substructures in Sparse Graphs, (9) Ramsey Theory for Graphs,
(10) Hamiltonian Cycles, (11) Random Graphs, and (12) Minors, Trees, and
WQO.
As far as the basic approach of the book is concerned, I just cannot state
it any better than the back-page review of the book does: ``Viewed as a
branch of pure mathematics, the theory of finite graphs is developed as
a coherent subject in its own right, with its own unifying questions and
methods. The book thus seeks to complement, not replace, the existing more
algorithmic treatments of the subject.''
The book is written in a thorough and clear style. The author puts special
emphasis on explaining the underlying ideas, and the technical details are
made as painless as possible. Some typographic novelties are introduced:
for example, there are little reminders on the margins to notations, definitions,
references. These may be helpful in following the text more easily; the
general outlook of a page, however, becomes sometimes a bit messy.
All in all, the book of R. Diestel is a smooth introduction to standard
material and is particularly rich source of deep results of graph theory.
I can highly recommend it to graduate students as well as professional mathematicians.
András Frank <frank@cs.elte.hu>
Optima
Newsletter of the Mathematical Programming Society
List of reviews
Return to home page