zbMATH — the first resource for mathematics

Graph theory. Foreword by Crispin St. J. A. Nash-Williams. (English) Zbl 0554.05001
Encyclopedia of Mathematics and Its Applications, Vol. 21. Menlo Park, California: Addison-Wesley Publishing Company. Advanced Book Program; Cambridge etc.: Cambridge University Press. XXI, 333 p. (1984).
This monograph intended as a textbook for advanced courses in graph theory is a unified and methodically excellent treatment of the current state of knowledge in this area. The reader is led to concepts, results and problems of the contemporary graph theory and is stimulated towards deeper studies. All theorems and other statements have appropriately detailed proofs and the prerequisites are kept to a minimum. Exercises, references, and historical and other notes at the end of each chapter round off the presentation. The terminology differs slightly from what the reader of the preceding book [Connectivity in graphs (1966; Zbl 0146.456)] of the same author may know. For example, the term ”polygon” is replaced by ”circuit”, and ”components modulo a subgraph J” by ”bridges of J”. As the author says in the introduction some parts of the text derive from his earlier papers (Chapters VIII,IX, and XI). In more detail the volume is arranged as follows: In Chapter I, basic concepts are introduced. The graphs dealt with in this book are finite and may have loops and multiple joins. Chapter II analyses the notion of a contraction, presents some theorems about vertices of attachment, and then states the Menger’s theorem and the Hall’s theorem. In the next two chapters, Chapter III and Chapter IV, one finds the development of the theory of 2-connectivity and 3-connectivity. Chapter V is devoted to the famous reconstruction problem and to its ”edge version”. In Chapter VI the concept of a digraph \(\Gamma\) is introduced. Both the vertex set and the dart set of \(\Gamma\) are supposed to be finite. Special attention is paid to Eulerian digraphs and the so called BEST theorem giving the number of Eulerian tours of \(\Gamma\) is proved. The matrix-tree theorem, the Kirchhoff’s laws, and the transportation theory are also included in this chapter. Author’s criterion for the existence of a 1-factor in a graph is one of the best known results in graph theory. Among other things the reader can find this theorem in Chapter VII. Chapter VIII is an attempt to describe some parts of graph theory algebraically. One section of this chapter touches briefly on matroids. Chapter IX deals with the dichromatic polynomials, the dichromates, the chromatic polynomials, and the flow-polynomials. Chapter X develops the theory of combinatorial maps by purely combinatorial axioms. The background for this part comes from the classical approach of H. R. Brahana (1921). Finally, problems related to the planarity are contained in Chapter XI. The duality of spanning trees, a combinatorial version of the Jordan’s theorem, the MacLane’s test and the Kuratowski’s test for the planarity are given here.
{The reviewer noticed a few misprints.}
Reviewer: J.Sedláček

05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05Cxx Graph theory
05B35 Combinatorial aspects of matroids and geometric lattices