Finding paths that visit every edge (Eulerian) or every vertex (Hamiltonian) exactly once.
Eulerian and Hamiltonian paths are two special types of paths in a graph that address specific traversal constraints. An Eulerian path is a trail in a graph that visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends on the same vertex. A graph has an Eulerian circuit if and only if it is connected and every vertex has an even degree. It has an Eulerian path if it is connected and has exactly zero or two vertices of odd degree. These can be found efficiently using algorithms like Hierholzer's algorithm. In contrast, a Hamiltonian path is a path in a graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Finding a Hamiltonian path is a much harder problem. In fact, determining whether a graph contains a Hamiltonian cycle is an NP-complete problem, meaning there is no known efficient (polynomial-time) algorithm to solve it for all graphs. While Eulerian paths have straightforward criteria and efficient solutions, Hamiltonian path problems often require backtracking, dynamic programming, or approximation algorithms for practical solutions on large graphs. Both concepts are fundamental in logistics, route optimization, and even computational biology.