In the 1700s, it was in Prussia and its name was Königsberg.

Here's a true story.

Once upon a time (OK, in the 18th century), in a place far away (well, Prussia), there once was a town called Königsberg. The townspeople enjoyed walking through their town and passing over the bridges spanning the river which passed through town. Over the years, a controversy arose and eventually word of it reached a very famous mathematician of the time, Leonhard Euler. Euler described the controvery himself in the following letter:

The problem, which I understand is quite well known, is stated as follows: In the town of Königsberg in Prussia there is an island called Kneiphhof, with the two branches of the river Pregel flowing around it. There are 7 bridges--a, b, c, d, e, f, and g--crossing the two branches. [as shown below]

The question is whether a person can plan a walk in such a way that he will cross each of these bridges once but not more than once. I was told that while some denied the possibility of doing this and others were in doubt, no one maintained that it was actually possible. On the basis of the above I formulated the following very general problem . . .

Euler went on to formulate a general theory which solved this particular problem and created a new branch of mathematics called graph theory.

Let's reconstruct Euler's solution to the bridge problem.

First, we will take a closer look at the bridges and the river.

Now let’s strip away some of the distractions:

Simplifying things once again:

A final simplification:

The figure above is called a graph. The dots are called vertices and the paths connecting the vertices are called edges. The graph is the fundamental structure in the field of graph theory. Euler used the graph above to solve the Königsberg bridge problem.

We will use graphs to solve routing problems.

The term, graph, is defined formally below.

GRAPH
A relational structure made up of vertices and edges. The edges of a graph express the relationships among the vertices.

Back