Hamiltonian path: Visit every vertex exactly once.
- NP-complete in general
- Solvable in O(n2⋅2n) with bitmask DP
- Feasible for n≤20
Euler path: Visit every edge exactly once.
- Polynomial time with Hierholzer's algorithm
- Check degree conditions first
How to tell them apart:
- "Visit every city once" = Hamiltonian
- "Travel every road once" = Euler
The difference in complexity is huge. Misidentifying costs you.
Space complexity is O(E) for the data structures used.