What is a Hamiltonian Path?

Hamiltonian path in the graph is a path that visits the each vertex exactly once. If such a path exists in the graph the graph is said to the have a Hamiltonian path. When the path starts and ends at the same vertex and it is called a Hamiltonian cycle or circuit.

Given a graph G(V, E), where V is the set of vertices and E is the set of edges, a Hamiltonian Path is a sequence of vertices (v₁, v₂, …,v_n) such that each vertex in V appears exactly once in the sequence, and for every i, 1<=i<n, there exists an edge (v_i, v_i+1) in E.

Example:

The Hamiltonian and Eulerian paths are two significant concepts used to the solve various problems related to the traversal and connectivity of the graphs. Understanding the differences between these two types of the paths is crucial for the designing efficient algorithms and solving the complex graph problems.