Had I not heard, unexpectedly, the term “dependency graph” during a recent design (more accurately, debugging) review of safety-critical software, in which review I was a third party along the lines of independent verification and validation (IV&V), I would have applied a non-negotiable skull-and-crossbones symbol to the software baseline under review. I have, among other things, Chartrand’s previous, no-nonsense graph-theory book [1] to thank for the serendipitous knowledge that I could bring to bear on this all-too-real venue. Although the presenting design team was comprised of highly competent (albeit compartmentalized) professionals, their development environment was at best an early 1970s-style mix of compilers, purely natural-language-based requirement enumerators, and detached configuration-control tools. Though these components were current, that is, twenty-first century, their mix was 1970s and lacked for example any counterpart of the model-based development advantage of logico-mathematical tool- and proof-based checking. Furthermore, it was as if the 1970s (let alone the present day) had not already felt the momentous presence of such giants as E. W. Dijkstra, C. A. R. Hoare, and D. L. Parnas. What is common to these latter three, and to their still all-too-rare ilk among practitioners, is mathematics.

In that regard, I recently found the following clever, humorous, and somewhat truth-bearing pronouncement (intended, I’m sure, as gender-neutral) on a web site [2]: “An engineer thinks that his equations are an approximation to reality. A physicist thinks reality is an approximation to his equations. A mathematician doesn’t care.” I hasten to add that the above alluded-to truth is at best a statistical one, but I nonetheless connect the mathematician part of the aphorism with the very first sentence of the book under review: “Mathematics rarely has the reputation we [the authors] feel it deserves.” The authors elaborate this reputation by reporting, to their chagrin, the oft-heard adjectives “boring” and “difficult” in this connection. I’ll add that many of us may also have heard “irrelevant” amazingly even from software “professionals”!

Mathematics’ potential constructions and constructs are indeed infinite in number. The late Austin J. Maher, my erstwhile boss and leading light in avionics software development and project management, occasionally alluded to “a solution looking for a problem.” Much of mathematics is certainly that, writ quite large. But I leave to such immortals as John von Neumann and Vladimir I. Arnold [3,4] to effect substantive, enlightening, and authoritative critiques of the field’s far and wide excursions into arguable irrelevance.

This book, whose subject is an arguably high mathematical abstraction, addresses von Neumann’s and Arnold’s issue, “by construction” (as I deem it) and in clear expository detail. It comprises a powerful antidote to what von Neumann [3] called the “art for art’s sake” purism that contributes to the public’s and, more importantly, young students’ wariness of mathematics, and indeed to its seeming (and sometimes real) sterility. The great C. F. Gauss is reputed to have been indifferent to the “pure” versus “applied” nature of his work, whereas G. H. Hardy made a sustained, lifelong point of pure mathematics’ superiority [5,6]. Frederick Soddy [7] replied memorably, “From such cloistral clowning, the world sickens.”

The book’s brief and charming prologue, which ends with delicious puns on, and variants of, Sondheim’s “Comedy Tonight” prologue, is enjoyable and highly informative, in a very palatable way. The chapters’ exercises are here said to exist “just in case a professor wants to use [this book] as a textbook.” (I would unhesitatingly adopt this excellent, and indeed fascinating, book as such.) The 12 chapters that follow the prologue are: “Introducing Graphs,” “Classifying Graphs,” “Analyzing Distance,” “Constructing Trees,” “Traversing Graphs,” “Encircling Graphs,” “Factoring Graphs,” “Decomposing Graphs,” “Orienting Graphs,” “Drawing Graphs,” “Coloring Graphs,” and “Synchronizing Graphs.”

This time, my habitual initial thumbing-through stopped in the middle of the book: chapter 9, “Orienting Graphs.” I would say that it was the luckiest of places, were it not for the essentially uniform distribution of masterfully intermingled human and mathematical interest throughout the book. Although biographical sketches appear in other science and mathematics texts these days, this book’s particular integration of the human and mathematical makes for optimal pedagogy. Chapter 9’s captivating tale of Herbert Robbins’s career, including Harvard versus West Point football and mathematics contests, will help to bind Robbins’s Theorem to all but the most uninterested of minds. And so it is with the other chapters, where what could have been low-effort spoon-feeding is instead gradual, careful, and context-rich build-up of graph-theory concepts, as in the first chapter, “Introducing Graphs”: “We begin with four problems ... all of [which] can be analyzed and eventually solved with the aid of a new sort of mathematical object[,] and that object is a graph.”

This book has my highest recommendation, certainly for students, but also for practitioners of high-assurance computing, where graph theory can be of great help in achieving such assurance.

More reviews about this item: Amazon, Goodreads