7.3 Eulerian Walks and Hamiltonian Cycles 1357.3 Eulerian Walks and Hamiltonian Cycles
Perhaps the oldest result in graph theory was discovered by Leonhard Euler,
the greatest mathematician of the eighteenth century.
FIGURE 7.8. Leonhard Euler 1707–1783It started with a recreational challenge that the citizens of K ̈onigsberg
(today, Kaliningrad) raised. The city was divided into four districts by
branches of the river Pregel (Figure 7.9), which were connected by seven
bridges. It was nice to walk around, crossing these bridges, and so the
question arose, is it possible to take a walk so that one crosses every bridge
exactly once?
KNEIPHOFFFIGURE 7.9. The bridges of K ̈onigsberg in Euler’s time, and the graph modeling
them.