Königsberg was a city in Prussia, situated on the Pregel river. This river flowed through the town and created two large islands. These islands were connected to the mainland by 7 bridges, as depicted in the image below.

Königsberg Bridges, image credit: Bogdan Giuşcă |

The answer to the question turns out to be "no" and a proof of this was published by Leonhard Euler in 1735. Euler's work laid the foundations of Graph Theory. Euler let each individual landmass represent a "vertex" (4 in all) and each bridge an "edge" (7 in all). The order of a vertex is the number of edges at that vertex. Euler showed that a graph such as this is only traversible if there are at most two vertices of odd order.

All four of the vertices in the Königsberg Bridge problem have odd order, and thus it is not possible to walk through town and cross each bridge only once.

## No comments:

## Post a Comment