Benjamin Co-authors Book on Graph Theory

What is the shortest route for a traveling salesman seeking to visit a number of cities in one trip? Or the minimum number of colors needed to fill in any map so that neighboring regions are always colored differently? These problems and more are encompassed by graph theory, the subject of The Fascinating World of Graph Theory, a book co-authored by Harvey Mudd Professor of Mathematics Arthur Benjamin and Western Michigan University mathematics professors Gary Chartrand and Ping Zhang.

Graph theory, also called network theory, is the mathematics often used to express relationships between objects, such as those in fields like transportation science, data structures and social media. Used across several academic disciplines, graph theory presents some of mathematics’ most wonderful and puzzling problems, sometimes with very elegant proofs.

For example: say you would like to prove that, among any six people, there must exist either three mutual friends or three mutual strangers. Label the people a, b, c, d, e and f. Person f must either have at least three friends or at least three strangers. Say that she has three friends: a, b and c. If any two of these people are friends (a and b, for example), then there would be three mutual friends (namely, a, b and f). Otherwise, no two of these people are friends, and therefore a, b and c are mutual strangers. (A similar argument works if f begins with three strangers.)

“I remember when I first read that proof when I was in college,’’ says Benjamin. “I was surprised by the statement, but even more excited by the logic used in its proof. Graph theory is full of unintuitive results with simple (and sometimes not-so-simple) explanations.”

At once playful and academically stimulating, The Fascinating World of Graph Theory, available from Princeton University Press, offers an assortment of such questions and puzzles that can be understood and solved by someone with a math background of high school algebra, says Benjamin. And it serves as more than just a tutorial—it also examines graph theory’s history, which dates back to the 18th century, as well as some of the brilliant individuals responsible for advancing the field.

Problems explored include classics such as the Königsberg Bridge Problem, the Chinese Postman Problem, a Knight’s Tour and the Road Coloring Problem. The book gives readers hands-on experience using a vast array of graphs, including bipartite and Eulerian graphs, the Petersen graph and tree graphs. Each chapter contains fun, challenging exercises.

Benjamin is no stranger to writing fun and accessible mathematics texts. He is the author of Secrets of Mental Math—a guide to performing his trademark Mathemagics—and Proofs That Really Count, a book on mathematical patterns. Benjamin credits Chartrand and Zhang as more experienced on the subject of graph theory, but believes his fresh take on the topic and entertaining approach to mathematics in general helps the book appeal to a general audience.

“The authors entice and enthuse readers through a number of fun problems which present various aspects of the subject,” says reviewer Robin J. Wilson, author of Introduction to Graph Theory. “Many of these problems are familiar, while others are less well known or of a more serious nature. This book can be used in different ways—as an entertaining book on recreational mathematics or as an accessible textbook on graph theory.”