Hamiltonian path: Visit every vertex exactly once.
- NP-complete in general
- Solvable in with bitmask DP
- Feasible for
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 for the data structures used.