Page 719 - Discrete Mathematics and Its Applications

698 10 / Graphs

a b a g f e a b

f c
g

d c b c d e d
G 1 G 2 G 3

FIGURE 7 Three Undirected Graphs.

be answered by determining whether there is an Euler path in the multigraph representing the
bridges in Königsberg. Because there are four vertices of odd degree in this multigraph, there
is no Euler path, so such a trip is impossible.
Necessary and sufficient conditions for Euler paths and circuits in directed graphs are given
in Exercises 16 and 17.

APPLICATIONS OF EULER PATHS AND CIRCUITS Euler paths and circuits can be used
to solve many practical problems. For example, many applications ask for a path or circuit that
traverses each street in a neighborhood, each road in a transportation network, each connection
in a utility grid, or each link in a communications network exactly once. Finding an Euler path
or circuit in the appropriate graph model can solve such problems. For example, if a postman
can find an Euler path in the graph that represents the streets the postman needs to cover, this
path produces a route that traverses each street of the route exactly once. If no Euler path exists,
some streets will have to be traversed more than once. The problem of finding a circuit in a graph
with the fewest edges that traverses every edge at least once is known as the Chinese postman
problem in honor of Guan Meigu, who posed it in 1962. See [MiRo91] for more information
on the solution of the Chinese postman problem when no Euler path exists.
Among the other areas where Euler circuits and paths are applied is in the layout of circuits,
in network multicasting, and in molecular biology, where Euler paths are used in the sequencing
of DNA.

Hamilton Paths and Circuits

We have developed necessary and sufficient conditions for the existence of paths and circuits
that contain every edge of a multigraph exactly once. Can we do the same for simple paths and
circuits that contain every vertex of the graph exactly once?

DEFINITION 2 A simple path in a graph G that passes through every vertex exactly once is called a Hamilton
path, and a simple circuit in a graph G that passes through every vertex exactly once is called
a Hamilton circuit. That is, the simple path x 0 ,x 1 ,...,x n−1 ,x n in the graph G = (V, E) is a
Hamilton path if V ={x 0 ,x 1 ,...,x n−1 ,x n } and x i
= x j for 0 ≤ i< j ≤ n, and the simple
circuit x 0 ,x 1 ,...,x n−1 ,x n ,x 0 (with n> 0) is a Hamilton circuit if x 0 ,x 1 ,...,x n−1 ,x n is
a Hamilton path.

This terminology comes from a game, called the Icosian puzzle, invented in 1857 by the
Irish mathematician Sir William Rowan Hamilton. It consisted of a wooden dodecahedron [a
polyhedron with 12 regular pentagons as faces, as shown in Figure 8(a)], with a peg at each
vertex of the dodecahedron, and string. The 20 vertices of the dodecahedron were labeled with
different cities in the world. The object of the puzzle was to start at a city and travel along the
edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the
first city. The circuit traveled was marked off using the string and pegs.