Walk in Graph Theory
In graph theory,
 A walk is defined as a finite length alternating sequence of vertices and edges.
 The total number of edges covered in a walk is called as Length of the Walk.
Walk in Graph Theory Example
Consider the following graph
In this graph, few examples of walk are
 a , b , c , e , d (Length = 4)
 d , b , a , c , e , d , e , c (Length = 7)
 e , c , b , a , c , e , d (Length = 6)
Open Walk in Graph Theory
In graph theory, a walk is called as an Open walk if
 Length of the walk is greater than zero
 And the vertices at which the walk starts and ends are different.
Closed Walk in Graph Theory
In graph theory, a walk is called as a Closed walk if
 Length of the walk is greater than zero
 And the vertices at which the walk starts and ends are same.
NOTE
It is important to note the following points

Path in Graph Theory
In graph theory, a path is defined as an open walk in which
 Neither vertices (except possibly the starting and ending vertices) are allowed to repeat.
 Nor edges are allowed to repeat.
Cycle in Graph Theory
In graph theory, a cycle is defined as a closed walk in which
 Neither vertices (except possibly the starting and ending vertices) are allowed to repeat.
 Nor edges are allowed to repeat.
OR
In graph theory, a closed path is called as a cycle.
Trail in Graph Theory
In graph theory, a trail is defined as an open walk in which
 Vertices may repeat.
 But edges are not allowed to repeat.
Circuit in Graph Theory
In graph theory, a circuit is defined as a closed walk in which
 Vertices may repeat.
 But edges are not allowed to repeat.
OR
In graph theory, a closed trail is called as a circuit.
NOTE
It is important to note the following points

Important Chart
The following chart summarizes the above definitions and is helpful in remembering them
Also ReadTypes of Graphs in Graph Theory
PRACTICE PROBLEMS BASED ON WALK IN GRAPH THEORY
Problem01:
Consider the following graph
Decide which of the following sequences of vertices determine walks.
For those that are walks, decide whether it is a circuit, a path, a cycle or a trail.
 a , b , g , f , c , b
 b , g , f , c , b , g , a
 c , e , f , c
 c , e , f , c , e
 a , b , f , a
 f , d , e , c , b
Solution
 Trail
 Walk
 Cycle
 Walk
 Not a walk
 Path
Problem02:
Consider the following graph
Consider the following sequences of vertices and answer the questions that follow
 x , v , y , w , v
 x , u , x , u , x
 x , u , v , y , x
 x , v , y , w , v , u , x
 Which of the above given sequences are directed walks?
 What are the lengths of directed walks?
 Which directed walks are also directed paths?
 Which directed walks are also directed cycles?
Solution
Part01:
 Only (A) and (B) are the directed walks.
 (C) is not a directed walk since there exists no arc from vertex u to vertex v.
 (D) is not a directed walk since there exists no arc from vertex v to vertex u.
Part02:
Both the directed walks (A) and (B) have length = 4.
Part03:
 Neither (A) nor (B) are directed paths.
 This is because vertices repeat in both of them.
 Vertex v repeats in Walk (A) and vertex u repeats in walk (B).
Part04:
 Neither of them are directed cycles.
 Walk (A) does not represent a directed cycle because its starting and ending vertices are not same.
 Walk (B) does not represent a directed cycle because it repeats vertices/edges.
Problem03:
Consider the following graph
Observe the given sequences and predict the nature of walk in each case
 v1e1v2e2v3e2v2
 v4e7v1e1v2e2v3e3v4e4v5
 v1e1v2e2v3e3v4e4v5
 v1e1v2e2v3e3v4e7v1
 v6e5v5e4v4e3v3e2v2e1v1e7v4e6v6
Solution
 Open walk
 Trail (Not a path because vertex v4 is repeated)
 Path
 Cycle
 Circuit (Not a cycle because vertex v4 is repeated)
To gain better understanding about Walk in Graph Theory,
Next ArticleGraph Coloring
Get more notes and other study material of Graph Theory.
Watch video lectures by visiting our YouTube channel LearnVidFun.