Unlike Eulerian paths, which are detectable in linear time [2], detecting Hamiltonian paths is NP-complete [3]. Does anyone have an intuitive explanation for why this is the case?
[1]: https://news.ycombinator.com/item?id=23123754
[2]: https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_alg...
Imagine building a Eulerian path. You're standing at a node, trying to figure out which edge to go down next. Eventually, because it's a Eulerian path, you'll have to go down all the edges eventually. This means it doesn't matter which edge you go down--even if your path hits a dead end, you can magically go back in time and patch in a cycle to your original path.
Put another way, if you establish that a graph has a Eulerian path, every maximal set of edge-disjoint cycles in the graph constitutes that path. Just by looking and making decisions at a very localized context (every node), you can formulate a correct answer.
By contrast, Hamiltonian paths are rarer. Only some maximal sets of node-disjoint cycles can be combined to construct a Hamiltonian path. You don't have the property that you can trivially patch the cycles together if you make a mistake. Looking at a node and trying to decide which next node to pick, you'd have to understand the structure of the entire graph very well to understand if traversing to A will screw you up, and the ramifications are not local.
[0]: https://www.amazon.com/Nature-Computation-Cristopher-Moore-d...