Posted by: Dave Richeson | September 25, 2008  Königsberg today
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 po