Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 159

Fig. 8-7

8.4Paths, Connectivity

A pathin a multigraphGconsists of an alternating sequence of vertices and edges of the form

v 0 ,e 1 ,v 1 ,e 2 ,v 2 , ..., en− 1 ,vn− 1 ,en,vn

where each edgeeicontains the verticesvi− 1 andvi(which appear on the sides ofeiin the sequence). The
numbernof edges is called thelengthof the path. When there is no ambiguity, we denote a path by its sequence
of vertices(v 0 ,v 1 ,...,vn). The path is said to beclosedifv 0 =vn. Otherwise, we say the path is fromv 0 ,tovn
orbetweenv 0 andvn,orconnectsv 0 tovn.
Asimple pathis a path in which all vertices are distinct. (A path in which all edges are distinct will be called
atrail.) Acycleis a closed path of length 3 or more in which all vertices are distinct exceptv 0 =vn. A cycle of
lengthkis called ak-cycle.

EXAMPLE 8.1 Consider the graphGin Fig. 8-8(a). Consider the following sequences:

α=(P 4 ,P 1 ,P 2 ,P 5 ,P 1 ,P 2 ,P 3 ,P 6 ), β=(P 4 ,P 1 ,P 5 ,P 2 ,P 6 ),

γ=(P 4 ,P 1 ,P 5 ,P 2 ,P 3 ,P 5 ,P 6 ), δ=(P 4 ,P 1 ,P 5 ,P 3 ,P 6 ).

The sequenceαis a path fromP 4 toP 6 ; but it is not a trail since the edge{P 1 ,P 2 }is used twice. The sequence
βis not a path since there is no edge{P 2 ,P 6 }. The sequenceγis a trail since no edge is used twice; but it is
not a simple path since the vertexP 5 is used twice. The sequenceδis a simple path fromP 4 toP 6 ; but it is
not the shortest path (with respect to length) fromP 4 toP 6. The shortest path fromP 4 toP 6 is the simple path
(P 4 ,P 5 ,P 6 )which has length 2.

Fig. 8-8

By eliminating unnecessary edges, it is not difficult to see that any path from a vertexuto a vertexvcan be
replaced by a simple path fromutov. We state this result formally.

Theorem 8.2: There is a path from a vertexuto a vertexvif and only if there exists a simple path fromutov.