path

A walk of a graph G =(X,E) is a sequence of the form:

where k is an integer ≥ 0, xi are vertices of G, and e_i are edges of G such that for i =0,...,k − 1, x_i and x_i+1 are the end vertices of e_i+1. The vertices x₀ and x_k are the ends of the walk, and we say that they are linked by the walk. The integer k is the length of the walk. A walk may have zero length. It is then reduced to a sequence containing only one vertex. When G is a simple graph, a walk may be simply defined by the sequence (x₀,x₁,...,x_k)of its

vertices. A sub walk of a walk is a walk defined as a subsequence between two vertices of the sequence defining the walk being considered.

A walk is called a trail if its edges e_i, for i =1,...,k are all distinct. Wesay that the walk does not go twice through the same edge.

A walk is called a path if its vertices xi, for i =0, 1,...,k are pairwise distinct. It should be noted that a path is necessarily a trail.

The following result is often useful for reasonings where walks are concerned.

Lemma 1.1.

In a graph, if two vertices are connected by a walk then theyare connected by a path.

proof.Given a walk linking the vertices x and x^/of a graph G and in which one vertex appears twice:

where x_i = x_j with 0 ≤ i<j ≤ k. The walk can be shortened by removing the subsequence (sub walk) between xi and x_j , which gives a new walk still linking x and x^/ .

By repeating this shortening process as long as there is a vertex that can befound twice in the walk, that is as long as the walk is not a path, we end up obtaining a path linking the vertices x and x^/ _.

Introduction to Graph Theory Second Edition, Douglas B. West , Indian Reprint, 2002,page(19)

Graph Theory  and Applications ,Jean-Claude Fournier,WILEY,page(29-31)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength