# 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