Les Réseaux (ou Graphes)

We thank Martin Charles Golumbic for the copy of his book M C Golumbic and André Sainte-Laguë, The zeroth book of graph theory - an annotated translation of Les Réseaux (ou Graphes) - André Sainte-Laguë (1926), Lecture Notes in Math. 2261 (Springer, Cham, 2021). This book contains the following dedication:-

Dedicated to the memory of André Sainte-Laguë's colleague, friend, and coauthor Guy Iliovici who was deported and murdered at Auschwitz by the Nazis and their collaborators.

We give below the Foreword and Introduction to the book.

Foreword

Michel Habib, Université de Paris

The appearance in 1926 of Les Réseaux (ou Graphes) was an important milestone in the historical development of graphs and their applications, from its first introduction by Euler (1735) with his famous problem on the bridges of Königsberg, to some early applications in chemical theory with the graphs of organic molecules. Most of the research in graph theory in the beginning of the last century still came from mathematical games and puzzles, but in his introduction, Sainte-Laguë seemed to be convinced of the great potential of applications of graph theory.

Sainte-Laguë's book was the first textbook devoted to the study of graphs, containing most of what was known at his time, as for example, the four color problem. In many aspects his book is very modern, by its subject, its presentation, and with many examples. It is interesting that many important notions had already been defined: trees, centres, chains, cycles, Eulerian cycles, Hamiltonian cycles, etc., although some of the notations are not the ones we use today.

Sainte-Laguë, through Édouard Lucas's books Récréations Mathématiques, knew about depth-first search that had been introduced to deal with searching labyrinths by Trémaux (1882) and Tarry (1895). Euler and many others after him developed what they called Analysis situs (Géométrie de situation in French). Lucas and Sainte-Laguë introduced the word graphe to the French community, describing this new domain in order to extract it from geometry and metrics.

The translation of Les Réseaux (ou Graphes) is excellent. It is not easy to translate such a text, since some definitions are obsolete and others incomplete or even false. Golumbic has succeeded in keeping as close as possible to the original text. His added footnotes, remarks, clarifications, corrections, and commentaries will be useful to the reader. I am happy to see this historically important work published in this English version.

Many of my students in computer science network theory are always surprised when I cite Sainte-Laguë's book. How could something so modern be so ancient?

Tracing the topics in Les Réseaux (ou Graphes)

Martin Charles Golumbic

In 1926, André Sainte-Laguë published a 65-page monograph entitled Les Réseaux (ou Graphes) which Harald Gropp has called the 'zeroth' book on graph theory [Poincaré and graph theory, Philosophia Scientiae 1 (1996), 85-95]. The monograph appeared only in French, but Gropp published a number of papers in English between 1993 and 2003 discussing historical aspects and giving a modern interpretation of several topics. He also expressed his hope that an English translation might sometime be available to the mathematics community.

In the 10 years following the appearance of Les Réseaux (ou Graphes), the development of graph theory continued, culminating in the publication of the first full book on the theory of finite and infinite graphs in 1936 by Dénes Konig [Theorie der endlichen und unendlichen Graphen (Akademische Verlagsgesellschaft, Leipzig, 1936)]. This remained the only well-known book for 20 years, until 1958 when Claude Berge published his book on the theory and applications of graphs [Théorie des Graphes et ses Applications (Wiley, 1958)]. By 1960, graph theory had emerged as a significant mathematical discipline of its own.

Les Réseaux (ou Graphes) provides historical testimony and a reminder of the excellent research in graph theory that had already been conducted at that time. Many of the concepts treated were still in their infancy, and other more developed notions offered a wealth of mathematical challenges. It is an important work, yet unfamiliar to most graph theorists.

By necessity, this book goes far beyond a mere straightforward translation. Dissecting, understanding, and converting concepts and terminology written a century ago, raised many difficult yet interesting challenges for presenting the work to a modern audience. We have annotated the text with over one hundred explanatory footnotes, provided remarks and commentaries on the original French, additional references, as well as supplementary comments by Alain Hertz, Myriam Preissmann and Robin Wilson. A casual reader, less interested in the specifics of the translation, may still appreciate these commentaries, in addition to the biography of André Sainte-Laguë that follows the translation.

A snapshot from 1926

Les Réseaux (ou Graphes) provides an important 'snapshot' of what was known about graph theory in 1926. Michel Habib describes it as a milestone on the road of graph theory and algorithms. André Sainte-Laguë was clearly influenced by the volumes of Édouard Lucas, Walter William Rouse Ball, Henri Poincaré, and others from the 1880s and 1890s, on what was then often considered to be recreational mathematics. With the perspective of more than a century of development, we now see this as a foundational period of combinatorics.

On the algorithmic side, graph traversal and depth-first search were already used by Tarry and Trémaux in the 1880s, and their very nice application to the computation of an Eulerian chain was given by Fleury in 1883.

Sainte-Laguë also prophetically understood that applications would play a future role in the development of the discipline. But it is doubtful that anyone in 1926 with a passion for mathematics, science, or technology, nor a forward-looking Jules Verne, could have imagined the Voyages Extraordinaires (Extraordinary Journeys) that graph theory has taken since. Not even H G Wells.

There are rather few citations of Les Réseaux (ou Graphes) in the literature. Konig cites it in his 1936 book [268] several times "and especially mentions his bibliographical list which was useful to him : : : to investigate the development of early graph theory in the French mathematical literature." [248]. An interesting historical perspective about Konig and his book can be found in [299].

W T Tutte wrote in [Les facteurs des graphes Annals of Discrete Mathematics 8 (1980), 1-5] (translated from the original French):

At Cambridge University, I found a work of Sainte-Laguë entitled Les Réseaux (ou Graphes). There is a proof of Petersen's theorem. I read. I understood. I filled the gaps. I even made a small improvement in the result of the text. 'Look at you,' I said to myself, 'You can work on networks. Perhaps the theory of graphs will be your research topic in the future!'

Sainte-Laguë's manuscript is listed in the biography of the historical book by Biggs, Lloyd and Wilson [Graph Theory: 1736-1936 (Clarendon Press, Oxford, 1998)] without further reference.

Sainte-Laguë's book begins its journey by introducing most of the basic definitions of graph theoretic notions commonly known at the time, using terminology that was both standard and non-standard in French. It then moves on to a variety of topics in graph theory at that time. He also published a short sequel [Géométrie de Situation et Jeux, Mémorial des Sciences Mathématiques No. 41 (Gauthier-Villars, Paris, 1929)], beginning by discussing the four color problem in more detail, and then moving on to graphs and games.

Translation is always a daunting task

Translating a mathematical text written over 90 years ago can be a formidable task. I have attempted to make the translation faithful to the original, yet occasionally a slightly freer translation is given to make it easier to read. Much of the translation uses terminology that is standard today, and which is different from that used by Sainte-Laguë. This decision was taken to help you to understand the concepts presented, thus serving as a basis of comparison. As an aid, a Glossary of translated terms has been added at the end of the book.

In some instances, however, there were no obvious translations of terms used by Sainte-Laguë. For example, his use of the term isthme is slightly more restrictive than today's usage of the term isthmus - namely, he did not consider a pendant edge (impasse) to be an isthme. Another example is the French word feuille, meaning a leaf, yet the current usage of the term leaf in graph theory is not the concept that Sainte-Laguë had in mind. We translate feuille as a leaf component whose definition is a subgraph obtained by deleting an isthmus, but which itself contains no isthmus. This translation was chosen to be analogous to the definition of a leaf block (membre) of a graph - namely, a subgraph that has no cut vertices and has only one vertex in common with the rest of the graph.

To maintain fidelity to the literal meaning of the presentation, illustrations (numbered figures) are the originals from his manuscript. His section numbering and format are maintained, to assist those who may read the French and English versions in tandem. I have also retained the mathematical notation used by Sainte-Laguë, even when it varies from section to section.

The process of proofreading the original French version also uncovered mathematical discrepancies and errors. These needed to be corrected in the translation - or sometimes had to be left alone with just a footnote.

The Bibliography begins with an edited version of the original appearing in the work. This is followed by further references cited in the commentaries and footnotes. The Glossary provides the French and English terms used in the book together with the section where they first appear.

Commentary

Sainte-Laguë had a reputation for integrating humor and personality into his presentations, first in his years of high school teaching, and later at the university attracting a thousand listeners at a time. Such elegance, however, is not reflected in this 1926 opus. There are no jokes, allusions, humorous mathematical bits, or fun puzzles to spice up this work. Nonetheless, I have taken the liberty of adding a few interesting footnotes and commentaries at the end of most chapters. For example, how many young readers today can describe a strip of postage stamps without seeing an example, or appreciate the art of a magic square?

Finally, I have written a short biography of André Sainte-Laguë to give a glimpse into his fascinating mathematical and non-mathematical career. To understand the importance of this work, it is worthwhile to see it in the context of his entire career.

Last Updated September 2023