# Seven Bridges of Königsberg

(Difference between revisions)
 Revision as of 13:11, 17 June 2009 (edit)← Previous diff Revision as of 13:55, 17 June 2009 (edit) (undo)Next diff → Line 20: Line 20: From here on we will use the word line instead of bridge, and vertex instead of From here on we will use the word line instead of bridge, and vertex instead of - Now we make the key observation that the walker must enter and exit every landmass. In order for this to be possible there must be an even number of br + Now we make the key observation that the walker must enter and exit every landmass. In order for this to be possible there must be an even number of lines at every vertex with the exceptions of the starting and finishing vertexes of the walk. For those two vertexes, an odd number of vertexes is permitted since the walker only exits the starting vertex and only enters the final vertex. - The German mathematician Carl Frederich Gauss solved this problem in... + Looking back at the last figure, we can see that all four vertexes have an odd number of lines. The existence of a path that could reach all four landmasses is impossible because it would go through more than two vertexes with odd number of lines. + + The German mathematician Carl Frederich Gauss solved this problem in 1735.

## Revision as of 13:55, 17 June 2009

Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historical problem that illustrates the foundations of graph theory.

# Basic Description

The setting of the problem is the city of Konigsberg in Prussia. The city is divided by a river with two islands. The four parts of the city are linked by seven bridges.

The problem is essentially to walk through the city and cross each bridge once and only once.

## Solution

While we could literally test out every possible case by hand, this would be extremely tedious and prone to error. Instead we will analyze the problem abstractly. By abstract, we mean to essentialize the problem; in this case, eliminating all features possible.

Our first step is to remove the distractions of the image itself.

From here we can make the observation that the size of the islands, sides of the river, and even the river itself are irrelevant. In addition the distances between the land masses are immaterial, thus the lengths of the bridges are irrelevant. Keeping these observations in mind, we resize the landmasses to points, and the bridges to lines.

From here on we will use the word line instead of bridge, and vertex instead of

Now we make the key observation that the walker must enter and exit every landmass. In order for this to be possible there must be an even number of lines at every vertex with the exceptions of the starting and finishing vertexes of the walk. For those two vertexes, an odd number of vertexes is permitted since the walker only exits the starting vertex and only enters the final vertex.

Looking back at the last figure, we can see that all four vertexes have an odd number of lines. The existence of a path that could reach all four landmasses is impossible because it would go through more than two vertexes with odd number of lines.

The German mathematician Carl Frederich Gauss solved this problem in 1735.