Graph theory. (English) Zbl 0182.57702

Addison-Wesley Series in Mathematics. Reading, Mass. etc.: Addison-Wesley Publishing Company. ix, 274 p. (1969).
It is difficult to imagine that a graph theorist exists whose personal library does not include Graph Theory by Frank Harary, for there is no other book on graph theory which contains the wealth of material that this does. Furthermore, the writing style of the author makes the reading easy and, on the whole, enjoy-able. This book might almost be classified as an encyclopedia on graph theory, due to the enormous number of concepts and theorems presented. A relatively small percentage of the theorems are proved, but this fits in with the manner in which the book is written. The one-word chapter titles (together with some additional comments on the contents) follow.
1. Discovery (“short stories” on various ways graphs were discovered by various people). 2. Graphs (contains most of the fundamental terms in graph theory; also includes Ramsey’s problem, extremal graphs, and operations on graphs). 3. Blocks (the structure of graphs, including cut-points and bridges). 4. Trees (presents numerous characterizations of trees; also contains a discussion of matroids). 5. Connectivity (contains many variations of Menger’s Theorem). 6. Partitions (in the sense of degree sequences). 7. Traversability (Eulerian graphs and Hamiltonian graphs). 8. Line-Graphs (including proofs of characterizations of graphs which are line-graphs). 9. Factorization (regular factorization and acyclic factorization). 10. Coverings (discussion of covering numbers and independence numbers). 11. Planarity (includes a proof of Kuratowski’s theorem; also contains discussion of genus, thickness, coarseness, and crossing number). 12. Colorability (includes a discussion of the Four Color Conjecture and a proof of the Five Color Theorem; also considers the Heawood Map, Coloring Theorem, chromatic-critical graphs, homomorphisms, and chromatic polynomials). 13. Matrices (the Matrix-Tree Theorem is proved here). 14. Groups (presents several operations on permutation groups; also discusses Cayley’s color-graph of a group and the \(n\)-cages). 15. Enumeration (Pólya’s Enumeration Theorem is proved; also a detailed discussion is given of solved and unsolved graphical enumeration problems). 16. Digraphs (digraph connectedness and tournaments).
With the exception of Chapter 1, each chapter is followed by a number of exercises ranging in difficulty from routine applications of the concepts to difficult research problems. Some attempt is made to categorize the problems according to their difficulty. However, since there is rarely a standard technique to employ on a combinatorics problem, no rating system on problems could expect to have more than mixed success.
The text is followed by appendices which give: (1) the number of graphs with \(p\) points and \(q\) lines, for \(p\leq 9\), (2) diagrams of all graphs with \(p\leq 6\) points, (3) the number of digraphs with \(p\) points and \(q\) arcs, for \(p\leq 8\), (4) diagrams of all digraphs with \(p\leq 4\) points, (5) the number of identity trees and homeomorphically irreducible trees with \(p\) points, for \(p\leq 12\), (6) the number of trees and rooted trees with \(p\) points, for \(p\leq 26\), (7) diagrams of all trees with \(p\leq 10\) points. The book concludes with an extensive bibliography; moreover, the text is well-referenced throughout.
The book also contains a Harary touch: Each chapter and major heading is preceded by a quote. Many of these are quite amusing. As a reference book for anyone whose interests include graph theory, this book is invaluable. No other book exists containing the information that Harary’s “Graph Theory” does. As a textbook on graph theory, this book would also be an excellent choice. It would probably prove most successful, however, if the instructor chose to cover a large number of concepts and not to prove every theorem. (In fact, one could illustrate graph-theoretic proofs by proving in class those theorems presented in Harary’s book.) Perhaps, proofs of some theorems could be left to the students.
In conclusion, Graph Theory is an extremely well-written book which contains a fantastic amount of information. It is valuable as a reference book or text book …or both.
Reviewer: G. Chartrand


05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx Graph theory