In this blog, we are going to discuss about Euler and Hamiltonian paths in a graph. We will start with basic terminologies related to paths in graph and describe elaborately about Euler Paths and Circuits, Hamiltonian Paths and Circuits with some examples that will get us clear with the fundamentals.
What is Graph?
A graph is a non-linear, complicated Data Structure that may be used to express complex interactions between items. A graph is made up of nodes (also known as vertices) linked by edges (also called arcs). There are several essential terms in graphs:
The term "neighbours" refers to two nodes that are connected by an edge.
The number of additional nodes to whom a node is linked determines its degree (i.e. the number of neighbours that it has)
An edge that connects a node to itself is called a loop.
A path is a collection of nodes connected by edges.
A closed path, or one that starts and finishes at the same node, is referred to as a cycle (and no node is visited more than once)
Euler or Hamilton Paths
An Euler path is a path that passes through every edge exactly once. If the euler path ends at the same vertex from which is has started it is called as Euler cycle.
A Hamiltonian path is a path that passes through every vertex exactly once (NOT every edge). Similarly if the hamilton path ends at the initial vertex from which it has started then it is known as Hamiltonian cycle.
Each edge of Graph 'G' appears exactly once, and each vertex of 'G' appears at least once along an Euler's route. If a linked graph G includes an Euler's route, it is traversable.
Example:
Euler’s Path: d-c-a-b-d-e
Euler Circuits
If an Euler's path if the beginning and ending vertices are the same, the path is termed an Euler's circuit.
Example:
Euler’s Path: a-b-c-d-a-g-f-e-c-a
Since the starting and ending vertex is the same in the euler’s path, then it can be termed as euler’s circuit.
Euler Circuit’s Theorem
If the number of vertices of odd degree in G is exactly 2 or 0, a linked graph 'G' is traversable. If a linked graph G contains exactly two vertices with an odd degree, it may include an Euler's route but not an Euler's circuit.
Note- This Euler route starts with an odd-degree vertex and concludes with another odd-degree vertex. .
Example:
Euler’s Path: b-e-a-b-d-c-a is not an Euler circuit but it is an Euler route. It clearly has two odd-degree vertices, i.e b, and a.
Note-If the number of vertices of odd degree = 0 in a connected graph G, Euler's circuit exists.
Hamilton’s Path
A Hamiltonian route is a simple path in graph G that travels through each vertex exactly once.
Example:
Hamilton Path : e-d-b-a-c
Note:
Each graph edge appears exactly once in Euler's circuit.
Some graph edges may be skipped in a Hamiltonian cycle.
Applications:
It is used in various fields such as Computer Graphics, electronic circuit design, mapping genomes, and operations research.
A very simple application is planning bus route to pick up students (node->student, road-> edges, bus path-> Hamiltonian path)
It is used in genome mapping to combine many tiny fragments of genetic code.
Hamilton’s Circuit
A Hamiltonian circuit is a simple circuit in graph G that runs through each vertex exactly once. Unlike Euler pathways and circuits, there is no easy criterion for determining if a graph has any Hamiltonian routes or circuits. However, several requirements rule out the existence of a Hamiltonian course in a graph, such as the presence of a vertex of degree one in the graph.
Certain theorems provide adequate but not required conditions for Hamiltonian graphs to existing.
Dirac’s Theorem
If G is a simple graph, with n vertices such that n >= 3, and the degree of each vertex of Graph G, is greater than n/2, the graph G has a hamilton circuit.
Ore’s Theorem
It Says that in a graph G with n vertices where n>=3, such that deg(u) + deg(v) >= n, for every nonpair adjacent vertices u and v, then G has hamilton circuit.
The above are sufficient conditions, not necessarily one for the existence of the Hamilton circuit in the graph.
Examples
Take a Look at the following graph:
Euler path exists – False
Euler circuit exists – False
A hamiltonian cycle exists – True
The hamiltonian path exists – True
G is not traversable because it contains four vertices with odd degrees. The graph contains a Hamiltonian cycle that passes over all vertices by bypassing the internal edges.
2. Does the following graph have a hamilton circuit?
Solution: No, the preceding graph does not include a Hamiltonian circuit since it has two vertices of degree one.
Frequently Asked Questions
Euler’s circuit vs hamilton circuit? Ans: A Hamiltonian circuit visits each vertex in a graph exactly once but may repeat edges, whereas an Eulerian circuit traverses every edge in a graph exactly once but may repeat vertices.
Let G be a complete undirected graph with n vertices and n > 2. The number of distinct Hamiltonian cycles in G will be ? Ans: A Hamiltonian circuit is a simple circuit in graph G that runs through each vertex precisely once. A Hamiltonian circuit with the same initial and final vertices is known as a Hamiltonian cycle. There are n permutations possible to visit each node in a full undirected graph with n vertices. However, based on these permutations, there are n possible places (i.e., nodes) from which to start and two different directions (clockwise or anticlockwise) in which to move. As a result, any one of this n! cycles belongs to a group of 2n cycles with the same edges. As a result, there are n!/2n=(n-1)!/2.
A given connected graph G is an Euler Graph if and only if all vertices of G are? Ans: A linked graph G is an Euler graph if all of its vertices are of even degree, and exactly two nodes have odd degrees, in which case the graph contains an Euler path but not an Euler circuit.
Conclusion
In this article, we learned about Euler’s Path, Euler Circuits, Euler circuit’s theorem, and Hamilton’s Path with some examples
I hope you understand the Euler and hamilton paths.
If you are a beginner, interested in computer fundamentals, and want to learn more about computer networks, you can look for our guided path, which is free!
8+ registered 