Page 700 - Discrete Mathematics and Its Applications

10.4 Connectivity 679

A formal definition of paths and related terminology is given in Definition 1.

DEFINITION 1 Let n be a nonnegative integer and G an undirected graph. A path of length n from u
to v in G is a sequence of n edges e 1 ,...,e n of G for which there exists a sequence
x 0 = u, x 1 ,...,x n−1 ,x n = v of vertices such that e i has, for i = 1,...,n, the endpoints x i−1
and x i . When the graph is simple, we denote this path by its vertex sequence x 0 ,x 1 ,...,x n
(because listing these vertices uniquely determines the path). The path is a circuit if it begins
and ends at the same vertex, that is, if u = v, and has length greater than zero. The path or cir-
cuit is said to pass through the vertices x 1 ,x 2 ,...,x n−1 or traverse the edges e 1 ,e 2 ,...,e n .
A path or circuit is simple if it does not contain the same edge more than once.

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 . This notation identifies a path only as far as which vertices it passes through.
Consequently, it does not specify a unique path when there is more than one path that passes
through this sequence of vertices, which will happen if and only if there are multiple edges
between some successive vertices in the list. Note that a path of length zero consists of a single
vertex.

Remark: There is considerable variation of terminology concerning the concepts defined
in Definition 1. For instance, in some books, the term walk is used instead of path,
where a walk is defined to be an alternating sequence of vertices and edges of a graph,
v 0 ,e 1 , v 1 ,e 2 ,..., v n−1 ,e n , v n , where v i−1 and v i are the endpoints of e i for i = 1, 2,...,n.
When this terminology is used, closed walk is used instead of circuit to indicate a walk that
begins and ends at the same vertex, and trail is used to denote a walk that has no repeated
edge (replacing the term simple path). When this terminology is used, the terminology path is
often used for a trail with no repeated vertices, conflicting with the terminology in Definition 1.
Because of this variation in terminology, you will need to make sure which set of definitions are
used in a particular book or article when you read about traversing edges of a graph. The text
[GrYe06] is a good reference for the alternative terminology described in this remark.

EXAMPLE 1 In the simple graph shown in Figure 1, a, d, c, f , e is a simple path of length 4, because {a, d},
{d, c}, {c, f }, and {f, e} are all edges. However, d, e, c, a is not a path, because {e, c} is not an
edge. Note that b, c, f , e, b is a circuit of length 4 because {b, c}, {c, f }, {f, e}, and {e, b} are
edges, and this path begins and ends at b. The path a, b, e, d, a, b, which is of length 5, is not
simple because it contains the edge {a, b} twice. ▲

Paths and circuits in directed graphs were introduced in Chapter 9. We now provide more
general definitions.

a b c

d e f

FIGURE 1 A Simple Graph.