Graphs: An Introduction

You can’t always tell a book by its title. The title of this book, for example, would reasonably lead a reader to believe that this was an introductory textbook for an undergraduate course in graph theory, but that’s not quite the case—a result that might not surprise any person familiar with XYZ Press. This publishing company was founded in 2008 by Titu Andreescu and specializes largely in contest preparation problem books, such as Lemmas in Olympiad Geometry and Problems From the Book. This book also falls into that category:  while it does contain some textual material on basic graph theory, I doubt that it is intended for, and is probably not, as explained below, really suitable as a text for an undergraduate course in graph theory.

 

The book is, except for two appendices (one on incidence and adjacency matrices, the other on probabilistic methods in graph theory), divided into two parts. The first part, about 130 pages long, discusses basic topics in elementary graph theory. It covers most of the “usual suspects” for a first undergraduate course (basic definitions, Eulerian and Hamiltonian graphs, trees, planar graphs, chromatic number, matchings, digraphs) and also some topics that are probably less standard (Ramsey theory, extremal graph theory, infinite graphs). This first part also contains, in addition to the text, a large number of exercises. The second part of the text, almost twice as long as the first, contains solutions to all of these. 

 

There are, as noted above, some potential problems with using this book as a text for a course. My guess is that there is not enough textual material in this ten-chapter book to fill out a standard 15-week undergraduate semester.  These deficiencies manifest themselves in several ways. First, a number of topics that one might want to cover in such a course are not discussed here; a few that come to mind are degree sequences and graph isomorphism.  The notion of isomorphism is quickly defined, but nothing really is done with this idea.  The general subject of connectivity, and results like Menger’s theorem that are generally associated with it, are also not discussed. The Havel-Hakimi theorem on degree sequences is also not mentioned.  The theory of edge colorings is also not discussed. I also don’t recall seeing the Petersen graph discussed at all; it seems to me that writing a book on graph theory and not mentioning this example is like writing a book on basic abstract algebra and not mentioning the symmetric group. 

 

In addition, even some of the topics that are mentioned are not done in the kind of depth that one might expect to find in a traditional undergraduate textbook. (Given that the textual part of the book is only 130 pages long, this is probably not surprising.) For example, in the chapter on trees (comprising 9 pages of actual text, not counting problems), the authors cover various equivalent definitions of a tree, spanning trees, and Cayley’s formula for the number of spanning trees of a complete graph.  However, there is no discussion of such things as minimal spanning trees, Prim’s algorithm, Kruskal’s algorithm, or other such topics. Likewise, the chapter on matchings in bipartite graphs includes a statement and two proofs of Hall’s Marriage theorem and an assortment of applications of it, but other topics, such the general topic of factorization in graphs, that are often covered in connection with this topic in graph theory texts, are not discussed.

 

Finally, although a number of results in the text are proved, some important results are not. An example is the Kuratowski criterion for planarity (the easy half is proved, but not the hard half). In connection with the four color theorem, the author proves that six colors suffice, but does not give the proof that five colors do. Graphs on other surfaces (e.g., the torus) are not discussed. 

 

The exercises in the book seem also to be of the “contest variety” rather than the “textbook variety”. Those that provide drill in the underlying ideas are in rather short supply. 

 

The bibliography is also geared towards problem-solvers rather than undergraduate students in a graph theory course. There are 28 entries, all of them, it would seem, referencing problem books.  All but four of these books list Andreescu as an author or co-author, and none of them list any of the standard textbooks in graph theory. 

 

In addition, there is no Index in the book at all. I view this as an appalling omission, one that should disqualify the book from consideration as a text. Unfortunately, this seems to be a fairly common occurrence with books published by XYZ Press. See, for example, the review of Number Theory: Concepts and Problems.  

 

Though probably not an optimal choice as a text for an undergraduate course, the book does have something to recommend it for other purposes. It is clearly written, requires minimal background on the part of the reader, often provides multiple proofs of a single result (thereby illustrating different techniques), and contains lots of problems. For these reasons, the book should prove useful as a contest-preparation tool. (As noted earlier, that is what it is likely intended for.) And a professor who is teaching an undergraduate course in graph theory might find this book valuable as a handy reference for additional problems. 

---

 

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.