Euler and Hamiltonian Paths

Harsh Goyal
Last Updated: May 13, 2022

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.

Hamiltonian Path and Circuits

A Hamiltonian path is defined as a path in a graph that passes through every vertex exactly once.

A simple circuit in a graph that passes through every vertex exactly once is called a Hamiltonian circuit. 

Hamiltonian Path and Circuit Criteria 

There are no simple, necessary, and sufficient criteria to determine if a path is hamiltonian or not, unlike Euler paths and circuits, but there are theorems that rule out the Hamiltonian circuit existence in a graph.

  • Dirac’s Theorem: If ‘G’ is a simple graph with ‘N’ vertices with N >= 3 and the degree of every vertex in ‘G’ is at least N / 2, then Graph ‘G’ has a Hamiltonian circuit.
  • Ore’s Theorem: If ‘G’ is a simple graph with ‘N’ vertices with N >= 3 and degree(U) + degree(V) >= N for every pair of non-adjacent vertices ‘U’ and ‘V’ in ‘G’ then ‘G’ has a Hamiltonian circuit.

The theorems mentioned above are sufficient but not necessary to prove the existence of a Hamiltonian circuit in a graph.

There are many practical applications of the Hamiltonian circuit, such as the Travelling Salesman Problem, which asks for the shortest route through a set of cities. This type of problem can be solved using this concept.

In the above graph, highlighted edges represent the hamiltonian path s -> u -> v -> w -> t.

Frequently asked questions

1) What is an Euler path?

Euler path is a path in a graph if it has exactly two vertices of odd degree and starts and end vertices are different.

 

2) What is a Hamiltonian Path?

A Hamiltonian path is defined as a path in a graph that passes through every vertex exactly once.

 

3) Can Hamiltonian Path Criterias confirm its availability in a graph?

No, the Criterias discussed in the hamiltonian path are sufficient but not necessary to prove the existence of a Hamiltonian circuit in a graph.

Key takeaways

This article discussed Euler and Hamiltonian Paths and the criteria to figure them out in the graph. 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
0 upvotes