Euler’s lines

Who doesn’t know it, the “House of Santa Claus”? The task is to draw the connecting lines between five points (in the figure 1, 2, 3, 4, 5) “in one go” so that each of these eight lines is crossed exactly once.

Figure 1: The house of Nicholas

One of many possible solutions to this problem is: 1-3-5-4-2-3-4-1-2. In MATHEMATICS ADVENTURE LAND you can find three similar tasks, where the task is to place a string over given lines exactly once around given points each. The more points and lines there are, the more difficult it is to find a solution.


And now … the mathematics of it:

The “House of Santa Claus” and the three figures shown in MATHEMATICS ADVENTURE LAND are — formulated mathematically — so-called undirected graphs. An undirected graph consists of a set of points with lines between them. The points are called nodes or vertices, the lines are called edges. Such a graph is called connected if every vertex is connected to every other vertex by a “path”, i.e. by a sequence of edges bound to each other (to vertices). The “House of Santa Claus” is such a connected graph. It has five nodes: 1, 2, 3, 4, 5 and eight edges: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4, 3-5, 4-5.

The simplest model in MATHEMATICS ADVENTURE LAND also represents a connected graph. It has 6 nodes and 12 edges.

Connected graphs are called Euler lines, “closed” Euler circle or Euler train after the mathematician Leonhard Euler (1707–1783). In mathematics (especially in its subfield of graph theory), it is a cycle that contains all edges of a graph exactly once. A connected graph that has an Eulerian line is also called an Eulerian graph. In 1736 Euler solved the so-called Königsberg bridge problem: The river Pregel flows through the former East Prussian Königsberg (since 1945 Russian: Kaliningrad). At the time of Euler, there were seven bridges across this branching river. The question was whether a circular route existed in which each bridge would be crossed exactly once.

Figure 2: The Königsberg bridge problem

If there is such a circular path, then the proof of its existence consists simply in showing this path. A serious mathematical problem, on the other hand, is to prove that such a path cannot exist. Leonhard Euler was able to prove in his “Solutio problematis ad geometriam situs pertinentis” that there is no such circular path if there are more than two islands or adjacent areas that can be reached by an odd number of bridges. Euler’s considerations led directly to graph theory as a subdiscipline of modern mathematics.


Literature

[1] Diestel, R.: Graphentheorie, 3. Auflage, Berlin / Heidelberg, 2006.

[2] Fellmann, E. A.: Leonhard Euler, Basel, 2006.

[3] Jungnickel, D.: Graphen, Netzwerke und Algorithmen, 3. Auflage, Darmstadt, 1994.

[4] Velminski, W.: Leonhard Euler. Die Geburt der Graphentheorie, Berlin, 2008.