Walks, Trails, Paths, Cycles and Circuits in Graph

Walk, trails, paths, cycles, and circuits in the graph are the alternate sequences of vertices and edges with different properties that in some sequences vertex and edge repetition is allowed, and in others, it is not allowed. In this article, we will explore walks, trails, paths, cycles, and circuits in graphs along with examples.

What is Walk?

A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk. 
Edge and Vertices can both be repeated.

Here, 1->2->3->4->2->1->3 is a walk.

Walk can be open or closed.

Types of Walks

There are two types of walks:

Open walk- A walk is said to be an open walk if the starting and ending vertices are different i.e. the origin vertex and terminal vertex are different. 
Closed walk- A walk is said to be a closed walk if the starting and ending vertices are identical i.e. if a walk starts and ends at the same vertex, then it is said to be a closed walk. 

In the above diagram: 
1->2->3->4->5->3 is an open walk. 
1->2->3->4->5->3->1 is a closed walk. 

What is Trail?

Trail is an open walk in which no edge is repeated, and vertex can be repeated. There are two types of trails: Open trail and closed trail. The trail whose starting and ending vertex is same is called closed trail. The trail whose starting and ending vertex is different is called open trail.

Here 1->3->8->6->3->2 is trail 
Also 1->3->8->6->3->2->1 will be a closed trail 

What is Circuit?

Traversing a graph such that not an edge is repeated but vertex can be repeated, and it is closed also i.e. it is a closed trail. 
Vertex can be repeated.
Edge cannot be repeated. 

Here 1->2->4->3->6->8->3->1 is a circuit.

Circuit is a closed trail.
These can have repeated vertices only.

What is Path?

It is a trail in which neither vertices nor edges are repeated i.e. if we traverse a graph such that we do not repeat a vertex and nor we repeat an edge. As path is also a trail, thus it is also an open walk. 

Another definition for path is a walk with no repeated vertex. This directly implies that no edges will ever be repeated and hence is redundant to write in the definition of path. 

Vertex not repeated 
Edge not repeated 

Here 6->8->3->1->2->4 is a Path 

What is Cycle?

Traversing a graph such that we do not repeat a vertex, nor we repeat an edge but the starting and ending vertex must be same i.e. we can repeat starting and ending vertex only then we get a cycle. In other words, cycle can be defined as the closed path.
Vertex not repeated 
Edge not repeated 

Here 1->2->4->3->1 is a cycle. 

Cycle is a closed path.
These cannot have repeat anything (neither edges nor vertices).

Note that for closed sequences start and end vertices are the only ones that can repeat. 

Table for Walk, Trail and Path

The table below represents the repetition of edges and vertices in walk, trail and path.

Solved Examples on Walks, Trails, Paths, Cycles and Circuits in Graph

1. Find a trail from A to D for below graph

A – B

| |

C – D

One possible trail is: A → B → D → C → A → B → D.

2. Find the shortest path from A to C.

A – B – C

| |

D – E

The shortest path is: A → B → C.

3. Finding All Possible Paths

A – B – C

| |

D – E

Following are paths

1. A → B → C
2. A → E → C
3. A → B → E → C

Practice Problems – Walks, Trails, Paths, Cycles and Circuits in Graph

Graph for Reference:

A

/|\

/ | \

B C D

\ | /

\|/

E

|

F

1. Find a path from A to F.
2. Find a simple path from B to F.
3. Find a trail that uses every edge exactly once.
4. Identify a cycle in the graph.
5. Find the shortest path from A to E.
6. List all possible paths from E to F.
7. Find a trail from C to F.
8. Find the longest simple path in the graph.
9. Count the number of distinct cycles in the graph.
10. Find a path from A to F that consists of exactly 3 edges.

Related Articles:

• Euler and Hamiltonian Paths | Engineering Mathematics
• Eulerian path and circuit for undirected graph

Walks, Trails, Paths, Cycles and Circuits in Graph – FAQs

What is Path and Trail in Graph Theory?

The path is sequences of vertices and edges with no repeated edge and vertices. A trail is sequence of vertices and edges in which vertices can be repeated but edge cannot be repeated.

What is a Cycle and Circuit in Graph Theory?

A cycle in graph theory is closed path in which both edges and vertices cannot be repeated. A circuit in graph theory is closed trail in which vertices can be repeated but edges cannot be repeated.

What is the Difference Between a Cycle and a Walk in Graph?

The difference between cycle and walk is that cycle is closed walk in which vertices and edges cannot be repeated whereas in walk vertices and edges can be repeated.

What is a Walk in Graph?

A walk in a graph is sequence of vertices and edges in which both vertices and edges can be repeated.

him0000

Follow

Improve

Article Tags :

• Engineering Mathematics
• GATE CS
• Mathematics
• Discrete Mathematics