Page 714 - Discrete Mathematics and Its Applications

10.5 Euler and Hamilton Paths 693

∗ 65. Use a graph model and a path in your graph, as in Exer- 66. Suppose that you have a three-gallon jug and a five-gallon
cise 64, to solve the jealous husbands problem.Two jug. You may fill either jug with water, you may empty
married couples, each a husband and a wife, want to either jug, and you may transfer water from either jug
cross a river. They can only use a boat that can carry into the other jug. Use a path in a directed graph to
one or two people from one shore to the other shore. show that you can end up with a jug containing exactly
Each husband is extremely jealous and is not willing one gallon. [Hint: Use an ordered pair (a, b) to indicate
to leave his wife with the other husband, either in the how much water is in each jug. Represent these ordered
boat or on shore. How can these four people reach the pairs by vertices. Add an edge for each allowable opera-
opposite shore? tion with the jugs.]

10.5 Euler and Hamilton Paths

Introduction

Can we travel along the edges of a graph starting at a vertex and returning to it by traversing
each edge of the graph exactly once? Similarly, can we travel along the edges of a graph starting
at a vertex and returning to it while visiting each vertex of the graph exactly once? Although
these questions seem to be similar, the first question, which asks whether a graph has an Euler
circuit, can be easily answered simply by examining the degrees of the vertices of the graph,
while the second question, which asks whether a graph has a Hamilton circuit, is quite difficult
to solve for most graphs. In this section we will study these questions and discuss the difficulty
of solving them. Although both questions have many practical applications in many different
areas, both arose in old puzzles. We will learn about these old puzzles as well as modern
practical applications.

Euler Paths and Circuits

The town of Königsberg, Prussia (now called Kaliningrad and part of the Russian republic),
was divided into four sections by the branches of the Pregel River. These four sections included
the two regions on the banks of the Pregel, Kneiphof Island, and the region between the two
branches of the Pregel. In the eighteenth century seven bridges connected these regions. Figure 1
depicts these regions and bridges.
Only five bridges connect
Kaliningrad today. Of The townspeople took long walks through town on Sundays. They wondered whether it was
these, just two remain possible to start at some location in the town, travel across all the bridges once without crossing
from Euler’s day. any bridge twice, and return to the starting point.
The Swiss mathematician Leonhard Euler solved this problem. His solution, published
in 1736, may be the first use of graph theory. (For a translation of Euler’s original paper see
[BiLlWi99].) Euler studied this problem using the multigraph obtained when the four regions
are represented by vertices and the bridges by edges. This multigraph is shown in Figure 2.
C

C

A
D A D

B
B
FIGURE 1 The Seven Bridges of Königsberg. FIGURE 2 Multigraph Model
of the Town of Königsberg.