The graph, when defined as a set of places and connections between them, can be used to describe a large number of situations. It began rather simply, as so many things have, with a problem posed to a talented mathematician. In this case, the problem was given to the great Leonard Euler. It was simple enough and dealt with the Old Prussian town of Konigsburg and the seven bridges that connected the two islands to the sections on the banks of the Pregel River. The question was a fundamental one, “Is it possible to walk across each bridge exactly once in a tour of the city?” Euler proved that it was not possible and in his reduction of the problem to locations and connections, inspired the invention of graph theory. His proof is so easy to understand that it is often presented in basic math classes.
Higgins improves on this, demonstrating some of the enormous variety of problems that graph theory can be applied to. Everything from family and hierarchical trees, manufacturing processes to modern computer connections are modeled using graphs. Graph theory is now so important that we offer a course in graph theory designed for computer science majors.
This book is a popular account of graph theory; nothing resembling a formal proof appears until the last chapter, which is reserved for that purpose. The exposition is clear and diagrams are included when needed. They are very helpful, clearly demonstrating the application of the technique described in the text. My favorite problem was circular Sudoku. My daughter has purchased over ten Sudoku books and has spent hours working the problems. I do not think it is a coincidence that her math grades have shown a significant improvement since she started working these problems.
This popular introduction to the history and applications of graph theory is as complete as such a work can be. It starts at the beginning and steps through many of the major problems that have made this such a valuable and necessary area of mathematics in the modern world.
Charles Ashbacher splits his time between consulting with industry in projects involving math and computers, teaching college classes and co-editing The Journal of Recreational Mathematics. In his spare time, he reads about these things and helps his daughter in her lawn care business.