Introduction to graph theory. 4th ed. (English) Zbl 0891.05001

Harlow: Longman. viii, 171 p. (1996).
The first edition of this successful book was published in 1972 (Zbl 0249.05101), its translation to Russian appeared in 1977 (Zbl 0365.05022), the second edition in 1979 (Zbl 0458.05024), and the third edition in 1985 (Zbl 0653.05020). For this new edition, the text has been completely revised, but the basic chapters and sections remain. Some terminology has been changed. There is new material on algorithms, tree searches, and graph-theoretical puzzles. In addition, solutions are given for selected exercises. These changes improved this attractive textbook. However, there are some places where the text could be still improved. E.g. in Figs. 2.5, 2.6, and 2.9, there are not all graphs but only simple graphs. In Exercise 14.7, one should “embed into” instead of “draw on” a Möbius strip. In the proofs of Theorem 29.1, the existence of a maximum flow remains open. Flow augmenting paths (p. 129) are no paths in digraphs. Due to printers there are wrong running heads in Chapter 7 and some symbols “\(|\)” replaced by “/” (p. 145-146). In spite of these minor comments, the book remains an outstanding introductory textbook on graph theory.


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