Page 701 - Discrete Mathematics and Its Applications

680 10 / Graphs

DEFINITION 2 Let n be a nonnegative integer and G a directed graph.A path of length n from u to v in G is a
sequence of edges e 1 ,e 2 ,...,e n of G such that e 1 is associated with (x 0 ,x 1 ), e 2 is associated
with (x 1 ,x 2 ), and so on, with e n associated with (x n−1 ,x n ), where x 0 = u and x n = v. When
there are no multiple edges in the directed graph, this path is denoted by its vertex sequence
x 0 ,x 1 ,x 2 ,...,x n . A path of length greater than zero that begins and ends at the same vertex
is called a circuit or cycle. A path or circuit is called simple if it does not contain the same
edge more than once.

Remark: Terminology other than that given in Definition 2 is often used for the concepts defined
there. In particular, the alternative terminology that uses walk, closed walk, trail, and path
(described in the remarks following Definition 1) may be used for directed graphs. See [GrYe05]
for details.

Note that the terminal vertex of an edge in a path is the initial vertex of the next edge in the
path. When it is not necessary to distinguish between multiple edges, we will denote a path
e 1 ,e 2 ,...,e n , where e i is associated with (x i−1 ,x i ) for i = 1, 2,...,n, by its vertex sequence
x 0 ,x 1 ,...,x n . The notation identifies a path only as far as which the vertices it passes through.
There may be more than one path that passes through this sequence of vertices, which will
happen if and only if there are multiple edges between two successive vertices in the list.
Paths represent useful information in many graph models, as Examples 2–4 demonstrate.

EXAMPLE 2 Paths in Acquaintanceship Graphs In an acquaintanceship graph there is a path between
two people if there is a chain of people linking these people, where two people adjacent in
the chain know one another. For example, in Figure 6 in Section 10.1, there is a chain of six
people linking Kamini and Ching. Many social scientists have conjectured that almost every
pair of people in the world are linked by a small chain of people, perhaps containing just five or
fewer people. This would mean that almost every pair of vertices in the acquaintanceship graph
containing all people in the world is linked by a path of length not exceeding four. The play Six
Degrees of Separation by John Guare is based on this notion. ▲

EXAMPLE 3 Paths in Collaboration Graphs In a collaboration graph, two people a and b are connected
by a path when there is a sequence of people starting with a and ending with b such that the
endpoints of each edge in the path are people who have collaborated. We will consider two
particular collaboration graphs here. First, in the academic collaboration graph of people who
have written papers in mathematics, the Erd˝os number of a person m (defined in terms of
relations in Supplementary Exercise 14 in Chapter 9) is the length of the shortest path between
m and the extremely prolific mathematician Paul Erd˝os (who died in 1996). That is, the Erd˝os
number of a mathematician is the length of the shortest chain of mathematicians that begins
with Paul Erd˝os and ends with this mathematician, where each adjacent pair of mathematicians
have written a joint paper. The number of mathematicians with each Erd˝os number as of early
2006, according to the Erd˝os Number Project, is shown in Table 1.
In the Hollywood graph (see Example 3 in Section 10.1) two actors a and b are linked when
there is a chain of actors linking a and b, where every two actors adjacent in the chain have
acted in the same movie. In the Hollywood graph, the Bacon number of an actor c is defined
to be the length of the shortest path connecting c and the well-known actor Kevin Bacon. As
new movies are made, including new ones with Kevin Bacon, the Bacon number of actors can
change. In Table 2 we show the number of actors with each Bacon number as of early 2011
Replace Kevin Bacon by
your own favorite actor to using data from the Oracle of Bacon website. The origins of the Bacon number of an actor
invent a new party game dates back to the early 1990s, when Kevin Bacon remarked that he had worked with everyone
in Hollywood or someone who worked with them. This lead some people to invent a party