Did You Know: The History of Graph Theory
Did You Know: The History of Graph Theory

Within the history of mathematics, the eighteenth century itself is commonly known as ‘The Age of Euler’ in recognition of the tremendous contributions that Euler made to mathematics during this period. The famous paper written by him on the Seven Bridges of Königsberg published in 1736 is considered as the first paper in the history of graph theory

Born in Basel, Switzerland, Leonhard Euler (1707 – 1783) studied mathematics under Johann Bernoulli (1667 – 1748), then one of the leading European mathematicians of the time and among the first — along with his brother Jakob Bernoulli (1654 – 1705) — to apply the new calculus techniques developed by Leibniz in the late seventeenth century to the study of curves. Euler soon surpassed his early teacher, and made important contributions to an astounding variety of subjects, ranging from number theory and analysis to astronomy and optics to mapmaking, in addition to graph theory and topology. His work was particularly important in re-defining calculus as the study of analytic functions, in contrast to the seventeenth century view of calculus as the study of curves. Amazingly, nearly half of Euler’s nearly 900 books, papers and other works were written after he became almost totally blind in 1771.

In a 1670 letter to Christian Huygens (1629 – 1695), the celebrated philosopher and mathematician Gottfried W. Leibniz (1646 – 1716) wrote as follows:

I am not content with algebra, in that it yields neither the shortest proofs nor the most beautiful constructions of geometry. Consequently, in view of this, I consider that we need yet another kind of analysis, geometric or linear, which deals directly with position, as algebra deals with magnitude.

Known today as the field of ‘topology,’ Leibniz’s ‘geometry of position’ was slow to develop as a mathematical field. As C. F. Gauss (1777 – 1855) noted in 1833,

Of the geometry of position, which Leibniz initiated and to which only two geometers, Euler and Vandermonde, have given a feeble glance, we know and possess, after a century and a half, very little more than nothing.

The ‘feeble glance’ which Euler directed towards the geometry of position consists of a single paper now considered to be the starting point of modern graph theory.

The paper appeared in Commentarii Academiae Scientiarum Imperialis Petropolitanae in 1736. In it, Euler undertakes a mathematical formulation of the ‘Königsberg bridge’ problem which was originated in the city of Königsberg, formerly in Germany but, now known as Kaliningrad and part of Russia, located on the river Preger. The city had seven bridges, which connected two islands with the main-land via seven bridges. People staying there always wondered whether was there any way to walk over all the bridges once and only once. The below picture is the map of Königsberg during Euler’s time showing the actual layout of the seven bridges, highlighting the river Preger and the bridges.

‘Königsberg bridge

‘Königsberg bridge’

Like other early graph theory work, the Königsberg Bridge Problem has the appearance of being little more than an interesting puzzle. Euler came out with the solution in terms of graph theory. He proved that it was not possible to walk through the seven bridges exactly one time. He abstracted the case of Königsberg by eliminating all unnecessary features. He drew a picture consisting of “dots” that represented the landmasses and the line-segments representing the bridges that connected those land masses. The resulting picture might have looked somewhat similar to the figure shown below.

Graph of Königsberg bridge

Graph of Königsberg bridge

This simplifies the problem to great extent. Now, the problem can be merely seen as the way of tracing the graph with a pencil without actually lifting it. One can try it in all possible ways, but you will soon figure out, it is not possible. But Euler not only proved that its not possible, but also explained why it is not and what should be the characteristic of the graphs, so that its edge could be traversed exactly once. He came out with the then new concept of degree of nodes. The Degree of Node can be defined as the number of edges touching a given node. Euler proposed that any given graph can be traversed with each edge traversed exactly once if and only if it had, zero or exactly two nodes with odd degrees. The graph following this condition is called, Eulerian circuit or path. We can easily infer this theorem. Exactly two nodes are, (and must be) starting and end of your trip. If it has even nodes than we can easily come and leave the node without repeating the edge twice or more.

Yet from such deceptively frivolous origins, graph theory has grown into a powerful and deep mathematical theory with applications in the physical, biological, and social sciences. The resolution of the Four Color Problem — one of graph theory’s most famous historical problems — even raised new questions about the notion of mathematical proof itself.

Four Colour Planar Graph

Four Colour Planar Graph

Möbius mentioned the problem in his lectures as early as 1840. The conjecture was first proposed on October 23, 1852 when Francis Guthrie, while trying to color the map of counties of England, noticed that only four different colors were needed. At the time, Guthrie’s brother, Frederick, was a student of Augustus De Morgan (the former advisor of Francis) at University College London. Francis inquired with Frederick regarding it, who then took it to De Morgan. According to De Morgan:

A student of mine [Guthrie] asked me to day to give him a reason for a fact which I did not know was a fact — and do not yet. He says that if a figure be any how divided and the compartments differently colored so that figures with any portion of common boundary line are differently colored — four colors may be wanted but not more — the following is his case in which four colors are wanted. Query cannot a necessity for five or more be invented… “

There were several early failed attempts at proving the theorem. De Morgan believed that it followed from a simple fact about four regions, though he didn’t believe that fact could be derived from more elementary facts.

One alleged proof was given by Alfred Kempe in 1879, which was widely acclaimed; another was given by Peter Guthrie Tait in 1880. It was not until 1890 that Kempe’s proof was shown incorrect by Percy Heawood, and in 1891 Tait’s proof was shown incorrect by Julius Petersen—each false proof stood unchallenged for 11 years.

In 1890, in addition to exposing the flaw in Kempe’s proof, Heawood proved the five color theorem and generalized the four color conjecture to surfaces of arbitrary genus. In 1943, Hugo Hadwiger formulated the Hadwiger conjecture, a far-reaching generalization of the four-color problem that still remains unsolved.

During the 1960s and 1970s German mathematician Heinrich Heesch developed methods of using computers to search for a proof. Notably he was the first to use discharging for proving the theorem, which turned out to be important in the unavoidability portion of the subsequent Appel-Haken proof. He also expanded on the concept of reducibility and, along with Ken Durre, developed a computer test for it. Unfortunately, at this critical juncture, he was unable to procure the necessary supercomputer time to continue his work.

While other teams of mathematicians were racing to complete proofs, Kenneth Appel and Wolfgang Haken at the University of Illinois announced, on June 21, 1976, that they had proven the theorem. They were assisted in some algorithmic work by John A. Koch.

If the four-color conjecture were false, there would be at least one map with the smallest possible number of regions that requires five colors. The proof showed that such a minimal counterexample cannot exist, through the use of two technical concepts:

  1. An unavoidable set is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable triangulation (such as having minimum degree 5) must have at least one configuration from this set.
  2. A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, then the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, then the original map can also. This implies that if the original map cannot be colored with four colors the smaller map can’t either and so the original map is not minimal.

The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of Jordan, Kuratowski and Whitney. Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist Gustav Kirchhoff, who published in 1845 his Kirchhoff’s circuit laws for calculating the voltage and current in electric circuits.

The introduction of probabilistic methods in graph theory, especially in the study of Erdős and Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as random graph theory, which has been a fruitful source of graph-theoretic results.

This modern controversy highlights the historical fact that standards of proof have always varied from century to century, and from culture to culture. This article will highlight one part of this historical story by examining the differences in precision between an eighteenth century proof and a modern treatment of the same result. In particular, we wish to contrast Euler’s approach to the problem of finding necessary and sufficient conditions for the existence of what is now known as an ‘Euler circuit’ to a modern proof of the main result of the paper.

About the author

Scientific History Blog Writer • Art enthusiast and Illustrator • Amateur Photographer • Biker and Hiker • Beer Enthusiast • Electrical Engineer • Chicago

Leave a Reply

Twitter Feed
%d bloggers like this: