In 1736 Leonhard Euler solved the now-famous bridges of Königsberg problem.  It is often hailed as the birth of topology and graph theory. Although no graph appears in Euler’s paper, his argument is topological in spirit. (He proved another famous topological theorem a decade and a half later.)

The problem is stated as follows. If a resident of Königsberg were to stroll through the city, would it be possible for her to cross all seven bridges without crossing one of them twice?  If so, is it possible to do so starting and ending at her house?  Below is a map of Königsberg from roughly that era.

The modern solution is to turn the problem into a graph theory problem.  Place a vertex on each landmass and add an edge for each bridge.  Euler discovered that there exists such a route if, and only if, there are zero or two vertices of odd degree (the degree of a vertex is the number of edges that meet at the vertex).  If there are zero, then it is possible to start and end at home.  If there are two, then the route must start and end on the landmasses of odd degree. As we see below, 1736 Königsberg has four vertices of odd degree.  So no such walk is possible.

On a whim, I decided to look for Königsberg and its bridges on Google Maps. (The city happens to be called Kaliningrad today.)

It turns out that two bridges are gone and there is one new one, so the graph is completely different! (There are several unidentifiable objects crossing the river.  I had to zoom in to see what is a bridge and what is not.) Unfortunately for the residents of Kaliningrad, there are still four vertices of odd degree.  So they still can’t take their city-wide stroll and not cross a bridge twice.