Introduction
This article will introduce Euler and Hamiltonian paths and discuss approaches to use them in different data structure problems.
Let’s start with understanding Euler Paths.
Euler Path
In Graph, An Euler path is a path in which every edge is visited exactly once. However, the same vertices can be used multiple times. So in the Euler path, the starting and ending vertex can be different.
There is another concept called Euler Circuit, which is very similar to Euler Path.
The only difference in Euler Circuit, starting and ending vertex should be the same in this case.
To Summarize -
- An Euler path is a path in a graph that uses every edge exactly once.
- An Euler path starts and ends at different vertices.
- An Euler circuit is a circuit in a graph that uses every edge exactly once.
- An Euler circuit starts and ends at the same vertex.
Euler Path Criteria
A graph has an Euler path if and only if it has exactly two vertices of odd degree. As a path can have different vertices at the start and endpoint, the vertices where the path starts and ends can have odd degrees.
Let’s take an example of the graph below, this graph has two vertices of odd degrees, ‘a1’ and ‘a3’ and the rest have even degrees. So this graph has an Euler path. Path is a1, a4, a3, a1, a2, a3.
Euler Circuit Criterias
A graph with at least two vertices has an Euler circuit if and only if each of its vertices has an even degree. The above statement is that each time a circuit passes through a vertex, the degree of that vertex is added twice. As it is a circuit, start and end vertices are the same, contributing one degree when the circuit starts and one when it ends. That’s how every vertex has an even degree.
Let’s take an example of the graph below, this graph has four vertices, all of the even degrees, so it has an Euler circuit. The circuit is a1, a3, a2, a1, a4, a3, a1.
116+ registered 