Königsberg Bridge ProblemThe problem is simply to find a path around a collection of bridges that crosses each bridge exactly once. The map below shows the layout of bridges in the town of Königsberg, with seven bridges and two islands. Map of KönigsbergThe seven bridges problem is well-known in both Maths and Computer Science, and so is particularly appropriate for the garden since the bridges problem links the two departments that sponsored the garden! It is usually associated with the 18thcentury mathematician Leonhard Euler --a path that solves the problem is called an Eulerian path. Eulerian paths have interesting properties, both mathematically and computationally. The layout of bridges is from the town of Königsberg in northern Germany (now part of Russia). The islands are in the middle of a river. In our garden the river is represented by the garden. Since it is a river, you aren't allowed to go around the far ends of the diamond! Euler is supposed to have proved that there is no solution when he was working in St.Petersberg. There could only be a solution if every island had an even number of bridges touching it, since one must leave an island the same number of times one arrives at it. Alternatively, exactly two islands can have anodd number of bridges, and these must be the start and finish point of the tour.
GraphsEuler's approach was to regard the spots of land (there are 4 of them) as points to be visited, and the bridges as paths between those points.The mathematical essentials of the map of Königsberg can then be reduced to the following diagram, which is an example of what is called a graph: A graph is a figure consisting of points (called vertices--the plural of vertex) and connecting lines or curves (called edges).The problem of the bridges of Königsberg can then be reformulated as whether this graph can be traced without tracing any edge more than once. For each of the vertices of a graph, the orderof the vertex is the number of edges at that vertex.The figure below shows the graph of the Königsberg bridge problem, with the orders of the vertices labeled. Euler's SolutionEuler's solution to the problem of the Königsberg bridges involved the observation that when a vertex is "visited" in the middle of the process of tracing a graph, there must be an edge coming into the vertex, and another edge leaving it; and so the order of the vertex must be an even number.This must be true for all but at most two of the vertices--the one you start at, and the