BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY S 0273-0979(99)00781-8 Article electronically published on April 21, 1999

Modern graph theory, by Béla Bollobás, Graduate Texts in Mathematics, vol. 184, Springer, New York, 1998, xiii + 394 pp., $59.95, ISBN 0-387-98488-7

Graph theory, by Reinhard Diestel, Graduate Texts in Mathematics, vol. 173, Springer, New York, 1997, xiv + 286 pp., ISBN 0-387-98211-6

Graph theory is one of mathematics’ precocious teenagers. Its growth is explosive. Its newly discovered connections with mainstream mathematics are breathtaking. It is difficult to decide what is fundamental, what will endure, and most of all where it will go next. These books bear witness to all of the above. The past twenty years have seen theorems that are important, elegant, surprising, powerful, and of course applicable. These texts begin to tell the story. Let me give three instances.

First, let ⪯ denote an ordering, a reflexive, transitive relation on a set X. Two classic orderings in graph theory are the topological minor relation—think subgraph homeomorphism—and the minor relation—think contraction. We say that G has a subgraph homeomorphic to H if the vertices of H can be identified with distinct vertices in G and the edges in H can be identified with edge disjoint paths in G. We say that G has H as a minor if H can be obtained from G by edge contractions together with vertex and edge deletions. If G has a subgraph homeomorphic to H, then G will contract to H by contracting the edge disjoint paths to single edges. Classically Kuratowski used homeomorphism to characterize planarity: a graph is planar if and only if it does not contain a subgraph homeomorphic to K_{5} or K_{3,3}. Subsequently Wagner established the same characterization using contraction. The Petersen graph shows that these two orderings are not identical. It has a subgraph homeomorphic to (and thus it contracts to) K_{3,3}, and it contracts to but does not have a subgraph homeomorphic to K_{5}.

If in every infinite sequence x_{1}, x_{2}, … drawn from X there are indices i < j such that x_{i} ⪯ x_{j}, then ⪯ is called a well-quasi-ordering of X. About forty years ago Kruskal [2] showed that the finite trees are well-quasi-ordered by the topological minor relation. Robertson and Seymour [3] have extended Kruskal’s result to show that the finite graphs are well-quasi-ordered by the minor relation. Ancillary results show that every hereditary graph property can be characterized by finitely many forbidden minors (this includes a Kuratowski theorem for arbitrary surfaces) and that testing for minors can be done in polynomial time. Diestel provides an engaging introduction to this material.

Second, suppose that A denotes the adjacency matrix of a graph; i.e. A_{i,j} = 1 if vertex i is adjacent to vertex j and 0 otherwise. Let D be the diagonal matrix whose entries denote the number of edges incident with a given vertex. The matrix L = D − A is called the Laplacian of the graph. It has been of continuing interest to relate graphical properties to the spectral properties of A and, following Alon and Milman [1], L. For instance if λ denotes the second smallest eigenvalue of L, then the connectivity of G is at least λ provided G is not a clique. This means that there are at least λ vertex disjoint paths between every pair of vertices. Even more

\begin{matrix}c \\ ◯ \end{matrix}1999 American Mathematical Society

1991 Mathematics Subject Classification. Primary 05-01, 05Cxx.

Research supported by NSA grant MSPF-96S-043.

impressive is that the edge boundary of a set of vertices U is at least \frac{λ|U||V −U|}{|V |}. Read Bollobás to begin thinking about algebraic graph theory.

Third, almost eighty years ago Pólya proved that a simple random walk on the d-dimensional integer lattice is recurrent if d = 1, 2 and transient if d ≥ 3. This turns out to be a special case of results on random walks on electrical networks. Bollobás provides an essentially self-contained introduction including material on hitting times and rapid mixing.

This is intriguing. Diestel talks about tree width and minors, but Bollobás doesn’t. Bollobás talks about algebraic graph theory and random walks, but Diestel doesn’t. Are these isolated instances? Not at all. Bollobás develops the Tutte polynomial, a generalization of the chromatic polynomial of a graph, and relates it to the much “Vaughnted” Jones polynomial of knot theory. Diestel mentions the Tutte polynomial in a chapter afternote. Diestel proves that the square of every 2-connected graph is Hamiltonian, while Bollobás looks at consequences of the Hamilton closure. To be sure, these books do have considerable overlap. The chapters on graph coloring show similar taste. Both books introduce Szemeredi’s regularity lemma, Ramsey theory, and random graphs. Neither book touches the connections with computational complexity. (This is a serious omission, since the geography of the NP-complete problems has had a profound impact on the graph theory esthetic.) Still, the overwhelming sense is that these authors have disparate views of what needs to be in a first graduate course.

These are graduate texts. As such a review ought to say a bit more than just what’s in the books. I like them both—a lot. Reading Diestel seems more like listening to someone explain mathematics. The author is generous with his insights. One unusual feature is that the book is full of margin notes indicating where in the text something is. At first this seemed as though it would be a distraction, but I am a convert. Bollobás is both longer and more dense. Each chapter begins with a prologue setting out where the chapter is going. Each chapter closes with an extensive set of engaging problems. So if you’re teaching a graduate course in graph theory, which do you choose? I would have my students use both.

References

[1] N. Alon and V. Milman, λ_{1}, isoperimetric inequalities for graphs, and superconcentrators, J. Combinatorial Theory B 38 (1985), 73-88. MR 87b:05092

[2] J. A. Kruskal, Well-quasi ordering, the tree theorem, and Vázsonyi’s conjecture, Transactions Amer. Math. Soc. 95 (1960), 210-225. MR 22:2566

[3] N. Robertson and P. D. Seymour, Graph minors, I-XV, J. Combinatorial Theory Ser. B 35, ..., 68 (1983, ..., 1996). MR 85d:05148, MR 86f:05103, MR 89m:05070, MR 89m:05071, MR 89m:05072, MR 91g:05039, MR 91g:05040, MR 91g:05041, MR 92g:05158, MR 94m:05068, MR 97b:05050, MR 97b:05088, MR 98d:05046, MR 99c:05056

Michael O. Albertson

Smith College

                                               E-mail address: albertson@math.smith.edu