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

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

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

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

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:

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>

Newsletter of the

List of reviews

Return to home page