Graph Theory An Introduction to Proofs, Algorithms, and Applications

Karin R. Saoub

Publisher:

Chapman and Hall/CRC

Publication Date:

2021

Number of Pages:

421

Format:

Hardcover

Price:

79.96

ISBN:

9781138361409

Category:

Textbook

MAA Review
Table of Contents

[Reviewed by

Tricia Muldoon Brown

, on

11/14/2021

]

Graph Theory is a textbook covering the traditional topics found in a college-level graph theory course designed for mathematics majors, including routes, trees, connectivity, matchings, and planarity. One thing that makes this book different is its flexibility to be used for graph theory courses with different prerequisites. Few assumptions are made about a student’s prior knowledge of proofs, and the needed proof techniques are introduced throughout the book in a just-in-time fashion. Thus a more introductory course on graph theory could spend more time on these beginning sections along with the applications, dealing lightly with the proofs. Proof topics covered consist of direct and indirect proofs, mathematical induction, if and only if statements, and algorithms. For courses that enroll students with a strong foundation in proofs, this introductory material can be discussed briefly and then the class can move on to more theoretical content. There is a nice outline at the beginning of the book suggesting schedules of topics for courses focusing more on theory or more on applications.

I think students will find that the language is very readable and not overly technical with good explanations and illustrating examples that help explain some of the extensive jargon found in graph theory. Different graph representations, matrices, vertex and edge sets, and planar pictures, are continually applied, and there are in text examples to test your knowledge before reading the solution. I also found the writing quite up-front and honest; for example the author admits on page 22 that they will “gloss over graph isomorphism” until it is needed later in the book. In terms of structure, the book has lots of black and white figures to illustrate. Definitions and examples are highlighted in gray boxes. It is quite complete with appendices on functions, set theory, matrices, algorithmic efficiency, and pseudocode. Each chapter has concrete computational exercises, but also proof exercises.

Chapters are typically introduced with an example and some background. Then the math concepts are covered with definitions, theorems, and proofs. More discussion follows, often returning back to the example, or weaving in historical details. I enjoy the places where you can get a little human context for the mathematicians behind the work. For example, in Chapter 3, I was interested to learn that both Prim and Kruskal built their spanning tree algorithms on work by a now lesser-known (to me) Czech mathematician Otakar Borůvka. There are also applications provided throughout the book with subjects such as RNA, 3D printing, snowplow routes, mazes, chemical graph theory, decision trees, or even seating

assignments on a train. (Although, the applications do tend to taper off as you get deeper into the text.) In particular, many of the applications and also more general questions are accompanied by the appropriate algorithm to solve the problem. These are written in pseudocode, so novice programmers should not expect to be able to plug these in and run calculations immediately. But they do illustrate the correct way to think about solving this type of problem in small examples.

I do wish this text was able to include color figures, and I did have to get over my, probably old-school, annoyance that words like “Eulerian” and “Hamiltonian” were uncapitalized, but I did enjoy the book. It certainly lives up to its subtitle as An Introduction to Proofs, Algorithms, and Applications.

Tricia Muldoon Brown (tmbrown @georgiasouthern.edu) is a Professor of Mathematics at Georgia Southern University with interests in combinatorics, commutative algebra, recreational mathematics, and sports.

See the publisher's website.

Tags:

Graph Theory