Notices of the American Mathematical Society
Welcome to the Notices of the American Mathematical Society.
With support from AMS membership, we are pleased to share the journal with the global mathematical community.
PDFLINK |
Graph Theory in America: The First Hundred Years
Communicated by Notices Associate Editor Emily Olson
Graph Theory in America
The First Hundred Years
By Robin Wilson, John J. Watkins, and David J. Parks. Princeton University Press, 2023, 320 pp., $35.
With great curiosity and summer enthusiasm, I hold the book in my hands. It is relatively light for a hardcover publication, excellent for reading during a casual vacation or other travels. Just a brief glimpse inside displays numerous pictures and photos. To my surprise, the book is in the grayscale; with growing curiosity I want to read it and see how the authors handle explanations of the history of the map-coloring problem without using colors. The foreword, written by Gary Chartrand, explains that the motivation for the book came from a question of one of his doctoral students, who inquired about the origins of math concepts and the way they developed. I appreciate this conscientious frame of mind, and I found myself wishing I used a more comprehensive and historical approach to mathematical concepts regularly with my students. In the Introduction, the authors clarify that the book is based on a doctoral dissertation of David J. Parks (the third author) written under the supervision of Robin Wilson (the first author) but gives no hints of the involvement of John J. Watkins (the second author), leaving the reader curious about the process of writing and publishing the book. The Introduction is followed by a list of Featured Papers, i.e., papers summarized later in the text. These summaries stand out in the text due to their placement on a darker background. The next part of the book is the Chronology of Events, which gives not only the years of the mathematical events featured in the book (between 1876 and 1976) but also provides additional historical brackets as early as 1636 and as late as 2021. At first impression, the book appears very much like a history book, but a deeper dive reveals the presence of rigorous mathematical proofs and a very neat mathematical formalism. Thus, it could make a good textbook for a course about the history of graph theory or a supporting textbook for a course in graph theory or discrete mathematics. Compared to literature in the area, the idea of presenting graph theory with significant historical background somehow resembles Biggs, et al. (1976) which covers the history of graph theory from 1736 to 1936. This book provides significant updates for recent history and includes many more nonmathematical aspects. In comparison to a standard textbook, written for example by Gary Chartrand himself (Chartrand, Zhang (2012)), this book does not offer as much variety in math topics, examples, and proofs. However, it is unique because it harmoniously weaves together threads of various natures: politics, society, colorful characters, wars, economics, and most importantly, mathematics.
The book is framed in American mathematics but includes necessary aspects of European episodes. It seems the authors were intentional in their placement so as not to disturb the logical and chronological flow. These European chapters are entitled “Interlude A” and “Interlude B.” Here, the European and American threads intertwine in a way that resembles my own life lived on two continents simultaneously. In this review, I will highlight not only the historical journey of a proof that spans centuries, but also my summer trip to Europe, which overlaps with my journey through the book.
The Development of the Four-Color Theorem and Other Historical Elements
The story begins with early American colleges of the seventeenth and eighteenth centuries; the oldest among these is the College of William and Mary in Williamsburg, Virginia. It is well-known that early American colleges were created based on traditional English schools and oriented toward teaching. It was not until Johns Hopkins University hired J.J. Sylvester that encouragement and facilities for research, especially mathematics research, began. The book provides a brief description about the funding of the institution and then a longer depiction of the personality of Sylvester. It highlights his writing style, which tightly and skillfully combined solid academic statements with human emotions, feelings, and impressions. Here is a quote from Sylvester’s paper published in 1878 displaying his eloquent style and a highly integrated mind:
In poetry and algebra we have the pure idea elaborated and expressed through the vehicle of language, in painting and chemistry, the idea enveloped in matter, depending in part on manual processes and the resource of art for its due manifestation.
Sylvester’s drawings of chemical diagrams presented in the book motivated work in algebra and graph theory. While this is a book about graph theory, it also includes tangential topics incorporated without chaos. Truly, after reading the first chapters it is already evident that only a highly integrated mind, in this case, three integrated minds, could create such a highly integrated book, without cacophony or even the slightest dissonance.
Another interesting feature of the book is the display of the first pages of historic articles and journals. For instance, early in the book we see the opening page of the first issue of the American Journal of Mathematics, published in 1878. Here names of well-known editors with colorful personalities whose complicated human interactions (also described in the book) are displayed in an excessive number of fonts. The book also touches upon the first appearance of Mathematical Reviews in 1940 by including its front page and the announcement. In opposition to the Zentralblatt fur Matematik, the Reviews were beyond the political and antisemitic disturbances of Europe, and their goal was to publish reviews of every mathematical research publication.
Nearly mundane, practical applications of actual map coloring performed by Alfred Bray Kempe motivated the problem of the coloring of maps with just four colors so that no two neighboring countries are colored the same. Amazingly, the authors reflect on the entire process of proving the coloring theorem, including the incomplete proof by Kempe in 1879. Reading about the process of creating the proof across centuries felt very educational; upon reflection, I am surprised this is often omitted from the college curriculum. Major threads of the proof are presented in detail, including Kempe’s patching process and further notes on that topic by W.E. Story. Human thinking has its meanders, and a generalization might illuminate a particular case. Percy John Headwood began considering the coloring problem on surfaces with different genus. Another generalization by George D. Birkhoff (in 1912) expresses in terms of chromatic polynomials the number of ways a given map can be colored with a given number of colors. Sister Mary Petronia Van Straten (whose photo is on page 163) is the only female noted in the book. Her contributions are related to the topology of graphs.
As World War I begins, the questions of mathematicians reflect the real-life experiences that brings more technology and different motivations to math problems (for example, in airplane designs). It was the war that delayed the publication of Oswald Veblen’s presentation Analysis Situs for Colloquium Lectures in Cambridge with his newly baked algebraic ideas that were later transformed by J.B. Listing to algebraic topology (topological complexes) and by G.R. Kirkhoff to electrical networks. At the same time, in another part of Europe, due to the outbreak of World War I, Kazimierz Kuratowski was not able to return from Poland (where I visited last summer) to his engineering studies in Scotland. Instead, as soon as the University of Warsaw reopened, he enrolled as one of the first mathematics students. Later, his characterization of planar graphs was published nearly at the same time as a similar proof by Orrin Fink and Paul A. Smith. As some of us know, simultaneous discoveries are a painful feature of mathematical research.
Partway through the text, the authors present a list of topics discussed in the book until this point. This roots the reader in the multitude of topics related to the four-color theorem and other milestones in the development of graph theory.
Multiple quotations enrich the text, giving a flavor of the style of writing and thinking of the mathematicians discussed. For instance, Hassler Whitney explains why he could not become a physicist by saying, “So I soon decided that since physics required learning and remembering facts, which I could not do, I would move into mathematics” (p. 123).
I was inspired by this quote as it could be inspirational to students and hopefully direct some of them to study mathematics. Among other contributions, Whitney improved the work of Birkhoff, his doctoral advisor, by applying to the chromatic polynomial the principle of inclusion and exclusion, which is now part of an introductory combinatorics course. In addition, he related graph theory to linear algebra, which is explained in this book with a list of correspondences.
The Overlap with My European Journey
This book is not constrained to only historical content; mathematical chapters are shuffled with historical chapters about World Wars I and II. These are complemented by descriptions of the human aspects of research such as human error and pride and social aspects such as lack of funding or social pressures. When I myself was leaving Hamburg, Germany, last summer, I read another surprising and lesser-known fact: Emil Artin was a refugee from Hamburg. Being married to Natalie Jasny, who was half Jewish, Artin had no tolerance for the growing antisemitism in Germany. He came to the US when he was forced to leave his job due to the famous paragraph 6 of the Act to Restore the Professional Civil Service issued by the Nazi government. I promised myself to search for traces of Artin in Hamburg when I visit next time.
The problem of flows in networks was motivated by a secret report on the Soviet Union and Eastern Europe performed by Ted Harris and was formulated as follows:
Consider a rail network connecting two cities by way of a number of intermediate cities. If each link of the network has a number assigned to it, representing its capacity, find a maximal flow from one city to the other.
Seeing in the book a map of Eastern Europe illustrating the problem made me feel sentimental. While on a ferry from Poland to Sweden last summer, I realized that all of the countries I visited on my vacation could be located on this map. As an application of graph theory, I could apply a search algorithm to determine if my trip had been planned efficiently. It seemed very fortuitous to me that the map Ted Harris posed in his paper inspired me to consider the problem of efficient routes from one city to another.
Graph theory got a serious boost from the introduction of computers and programing. For early computers, the question of complexity of algorithms was particularly crucial. The input size influences the running time and could force researchers to wait for their results until the end of the universe if they did not consider the complexity of the algorithms. In 1971 Stephen Cook introduced the satisfiability problem which can be solved in NP time and has the property that a vast number of other NP problems can be converted to it in polynomial time. The list of NP problems is long and contains, for example, the travelling salesman problem, determining the existence of a Hamiltonian cycle in a graph, and the question of whether two graphs are isomorphic.
Again, my travels aligned with the book when I was reading about Heinrich Heesch receiving his doctorate from the University of Zurich and his work on the four-color theorem. Heesch combined the ideas of unavoidable sets of configurations and reducible configurations into the idea of unavoidable sets of reducible configurations. He was hoping to prove the four-color theorem by checking ten thousand configurations, literally testing one per day. Wolfgang Haken had the idea to use computers to check the configurations, though he ran into the problem of prolonged waiting time for large sets. Once back in New York City and having returned to my academic work at CUNY, I read that Kenneth Appel, a CUNY graduate from Queens College, offered his expertise in programming and his contributions allowed much faster progress. Page 238 contains a sample of reducible configurations with original computer printout. The next page contains 35 drawings of reducible configurations from the paper which announced the proof that every planar graph is four-colorable. This, however, does not end the book. The chapter entitled “Aftermath” summarizes the consequences of the growth of graph theory. Multiple conferences and proceedings were followed by numerous books on the four-color theorem and more generally, graph theory. In the explosion of graph theory discourse, new research directions and new connections were developed.
Conclusion
The book concludes with a few closing sections. An alphabetical Glossary of mathematical terms, algorithms, and theorems allows a reader to quickly find a forgotten term. Notes, References, and Further Reading contain a list of articles and books organized by chapter. Acknowledgements and Picture Credits (somehow placed together) attribute shared efforts of multiple institutions and individuals from America and Europe. Pictures of mathematicians, their hand drawings, and first pages from their papers are listed here with helpful attributions. The book ends with an Index of terms used in the book.
I know that it was not the intention of the authors but in my humble opinion, adding some open problems for the reader to consider would add a lot to this already rich book. I wish that possible future editions of this book would accommodate colorful pictures. I hope that the authors will continue writing and publishing in this style.
To summarize, the book is an excellent display of the detailed mathematical history of the map coloring problem and other accompanying problems, such as graph planarity and P- or NP-completeness. It is a blend of mathematical and historical facts that make an accessible read for interested students at a high school or college level. I would say that anyone with any background in mathematics would benefit from reading this book. I enjoyed being immersed in the type of exposition which highlights not only the topic itself but places it in the historical and biographical context across the centuries and countries, and I believe many college instructors could incorporate it into their teaching. I am hoping that new generations of mathematicians will grow more aware of the historical and epistemological aspects of mathematics, as I did after reading this book. I wish for more publications like this.
References
- [1]
- Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, Graph theory. 1736–1936, 2nd ed., The Clarendon Press, Oxford University Press, New York, 1986. MR0879117,
Show rawAMSref
\bib{Biggs}{book}{ author={Biggs, Norman L.}, author={Lloyd, E. Keith}, author={Wilson, Robin J.}, title={Graph theory. 1736--1936}, edition={2}, publisher={The Clarendon Press, Oxford University Press, New York}, date={1986}, pages={xii+239}, isbn={0-19-853916-9}, review={\MR {0879117}}, } - [2]
- G. Chartrand and P. Zhang, A First Course in Graph Theory, Dover Publications, Dover Books on Mathematics, 2012.
- [3]
- J. J. Sylvester, On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics, With Three Appendices, [Continued], Amer. J. Math. 1 (1878), no. 2, 105–125, DOI 10.2307/2369302. MR1505156,
Show rawAMSref
\bib{Sylvester}{article}{ author={Sylvester, J. J.}, title={On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics, With Three Appendices, [Continued]}, journal={Amer. J. Math.}, volume={1}, date={1878}, number={2}, pages={105--125}, issn={0002-9327}, review={\MR {1505156}}, doi={10.2307/2369302}, }
Małgorzata Marciniak is an associate professor of mathematics at LaGuardia Community College of the City University of New York. Her email address is mmarciniak@lagcc.cuny.edu
Article DOI: 10.1090/noti2853
Credits
Book cover is courtesy of Princeton University Press.
Photo of Małgorzata Marciniak is courtesy of Małgorzata Marciniak.