Graph theory

          PATHS, CONNECTIVITY

A path in a multigraph G consists of an alternating sequence of vertices and edges of the form

v₀,      e₁,      v₁,       e₂,      v₂,      . . . ,      e_n?1^,v_n?1^,e_n,                      v_n

where each edge e_icontains the vertices v_i?1^andv_i(which appear on the sides of e_iin the sequence). The

number n of edges is called the length of the path. When there is no ambiguity, we denote a path by its sequence

of vertices (v₀, v₁, . . . , v_n). The path is said to be closed if v₀= v_n. Otherwise, we say the path is from v₀, to v_n

or between v₀and v_n, or connects v₀to v_n.

A simple path is a path in which all vertices are distinct. (A path in which all edges are distinct will be called

a trail.) A cycle is a closed path of length 3 or more in which all vertices are distinct except v₀= v_n. A cycle of

length k is called a k-cycle.

EXAMPLE 8.1   Consider the graph G in Fig. 8-8(a). Consider the following sequences:

? = (P₄, P₁, P₂, P₅, P₁, P₂, P₃, P₆),                     ? = (P₄, P₁, P₅, P₂, P₆),

? = (P₄, P₁, P₅, P₂, P₃, P₅, P₆),

                                                          ? = (P₄, P₁, P₅, P₃, P₆).