Section 7.2 Euler Path and Hamiltonian Circuit
571
S e c t i o n 7 . 2 euler path anD hamiltonian CirCuit
euler Path Problem
The Euler path problem (the highway inspector problem) originated many years
ago. Swiss mathematician Leonhard Euler (pronounced “oiler”) (1707–1783) was
intrigued by a puzzle popular among the townsfolk of Königsberg (an East Prussian city later called Kaliningrad, which is in Russia). The river flowing through
the city branched around an island. Various bridges crossed the river as shown in
Figure 7.4.
b
a
c
d
Figure 7.4
The puzzle was to decide whether a person could walk through the city crossing
each bridge only once. It is possible to answer the question by trial and error, listing (or walking) all possible routes, so some dedicated Königsberger could have
solved this particular puzzle. Euler solved this problem, and indeed a more general
version of the problem, by a better mechanism than trial and error. The problem
is usually represented as a graph (Figure 7.5) where the bridges are arcs and the
land masses (labeled a through d ) are nodes. The more general question is to determine when an Euler path exists in any graph.
1
d
a
c
b
Figure 7.5
1 Euler did not actually represent the problem as a graph, and such a representation was not connected to
Euler’s work until over 150 years later. See “The Truth about Königsberg” by Brian Hopkins and Robin
Wilson, The College Mathematics Journal, May 2004.