The Birth of Graph Theory: Leonhard Euler and the Königsberg Bridge Problem

views updated

The Birth of Graph Theory: Leonhard Euler and the Königsberg Bridge Problem

Overview

The good people of Königsberg, Germany (now a part of Russia), had a puzzle that they liked to contemplate while on their Sunday afternoon walks through the village. The Preger River completely surrounded the central part of Königsberg, dividing it into two islands. These islands were connected to each other and to the mainland by seven bridges. The puzzle, which baffled the residents of Königsberg was this: Was it possible to pick a starting point in the town and find a walking route which would take them over each bridge exactly once? No one had ever found such a route; but did that mean that it did not exist? The problem caught the attention of the great Swiss mathematician, Leonhard Euler. Euler was able to prove that such a route did not exist, and in the process began the study of what was to be called graph theory.

Background

Leonhard Euler (1707-1783) is considered to be the most prolific mathematician in history. Originally educated for the ministry in order to follow in his father's footsteps, Euler discovered his talents in mathematics while attending the University of Basel. By 1726, the 19-year-old Euler had finished his work at Basel and published his first paper in mathematics. In 1727, Euler assumed a post in St. Petersburg, Russia, where he spent fourteen years working on his mathematics. Leaving St. Petersburg in 1741, Euler took up a post at the Berlin Academy of Science. Euler finally returned to St. Petersburg in 1766, where he would spend the rest of his long, productive life.

Euler worked, wrote, and published at a furious rate throughout his lifetime. Although blind for the last seventeen years of his life, he continued to work and write (with the help of various assistants and secretaries) at an astonishing rate. Euler worked in almost every branch of mathematics, both pure and applied, and his ability to perform complicated mathematical calculations in his head was legendary. Supported most of his life by the Berlin Academy and the St. Petersburg Academy, Euler worked with the famous Bernoulli family (Johannes, Daniel, and Nicolaus), as well as many other famous mathematicians. So it is no surprise that when Euler decided to analyze the problem of the Königsberg bridges, he not only found the answer, but also initiated the study of a brand new field in mathematics.

Here is how Euler went about solving the Königsberg Bridge Problem. The first step was to transform the actual diagram of the city and its bridges into a graph. The use of the word graph in this context may be different than what most people think of when they see the word graph. In this case, a graph must have vertices and edges. Furthermore, a graph must have a rule that tells how the edges join the various vertices. In the Königsberg Bridge Problem, the vertices represent the landmasses connected by the bridges, and the bridges themselves are represented by the edges of the graph. Finally, a path is a sequence of edges and vertices, just as the path taken by the people in Königsberg is a sequence of bridges and landmasses. Euler's problem was to prove that the graph contained no path that contained each edge (bridge) only once.

Actually, Euler had a larger problem in mind when he tackled the Königsberg Bridge Problem. He wanted to determine whether this walk would be possible for any number of bridges, not just the seven in Königsberg. To answer this question, Euler studied other graphs with various numbers of vertices and edges. Euler reached several conclusions. First, he found that if more than two of the land areas had an odd number of bridges leading to them, the journey was impossible. Secondly, Euler showed that if exactly two land areas had an odd number of bridges leading to them, the journey would be possible if it started in either of these two areas. Finally, Euler concluded that if there were no land areas with an odd number of bridges leading to them, the journey was possible starting from any area. At first glance, Euler's work seems to apply only to the trivial matter of walking through a city connected by bridges over a river. Of course, his conclusions were actually more general when the land areas were considered vertices of a graph and the bridges were the edges of the graph. Thus was born the modern mathematical study of graph theory. A path in which one may "walk" along each edge exactly once has come to be called a "Eulerian path," and an "Eulerian graph" is a graph in which such a path exists.

Impact

That such a seemingly trivial problem could lead to an entire branch of mathematics is not unusual. Although some areas of mathematics were developed to answer obviously important questions (for instance, calculus was developed by Isaac Newton (1642-1727) to help answer questions in physics and astronomy), others branches of mathematics had their origins in much less noble causes (the origination of probability is traced to letters exchanged by Pierre de Fermat (1601-1665) and Blaise Pascal (1623-1662) in which they discussed questions in gambling). Although the branch of mathematics known today as graph theory had its origins in a simpleminded puzzle that entertained the people of Königsberg, its eventual usefulness to mathematics has completely overshadowed its humble beginnings. For instance, chemists use graphical notation to represent chemical compounds; and physicists and engineers use graphical notation to represent electrical circuits. Graph theory is used in complex computer programs that control telephone switching systems.

Graph theory is a part of a larger field of mathematics called topology. Topology is the study of the properties of geometric figures that are invariant (do not change) when undergoing transformations such as stretching or compression. Imagine drawing a geometric figure, such as a square or a circle, on a sheet of flexible material like rubber, and then stretching or compressing the rubber sheet. The properties of the square and circle that do not change during this stretching or compression fall under the study of topology. For this reason, topology is sometimes referred to as "rubber-sheet geometry."

Euler called this type of mathematics "the geometry of position," because it did not address magnitude, as did traditional geometry. Topology and graph theory investigate position without the use of measurement (it does not matter how long the bridges are or how far the land masses are from each other.) In addition to his work on the Königsberg Bridge Problem, Euler proved that for any polyhedron, the number of vertices minus the number of edges plus the number of faces was always equal to two (v-e+f=2). For instance, a cube has eight vertices, twelve edges, and six faces (8-12+6=2). It is generally accepted that Euler's solution of the Königsberg Bridge Problem and his famous formula for a polyhedron form the foundation of the field of topology.

There are other problems similar to the Königsberg Bridge Problem that fall under the heading of graph theory. Euler worked on another of these famous problems called the "Knight's Tour Problem." This problem asks if a knight on a chessboard can be successively moved (the familiar two squares one direction and then one in the perpendicular direction) so that it visits each square on the board only once and then finishes on the same square as it began. Another of these problems is known as the "Traveling Salesman Problem." In this problem, a salesman is required to visit a certain number of cities, taking the path that will mean the shortest total distance, and ending up back in the city in which he started. With the cities being represented as vertices and the paths to each city represented as edges, this becomes a graph much like the Königsberg bridges.

Possibly the most famous application of graph theory is the Four-Color Problem. This problem was first proposed by Francis Guthrie through his brother, Frederick, to the London mathematician Augustus DeMorgan (1806-1871) nearly a century after Euler's death. The Four-Color Problem asks the seemingly simple question "How many colors must be used to color any map so that no two adjacent land areas (country, states, etc.) are the same color?" The problem may be posed as one in graph theory if the land areas are represented as vertices and the adjacent areas are connected by edges. Although the answer of four colors was suspected for over a century, it was not until 1976 that a proof was found that confirmed that four colors were required. The Four-Color Problem was the first major mathematical theorem whose proof depended in part on modern computers.

Each of these problems, although trivial on the surface, has led to incredible advances in mathematical theory and applications. From its innocent beginnings in the speculations of the people of Königsberg, to Euler's pioneering work, through modern applications, graph theory has had a profound effect on mathematics and its applications for over 250 years.

TODD TIMMONS