Pattern: Hamiltonian vs Euler

Hamiltonian path: Visit every vertex exactly once.

• NP-complete in general
• Solvable in $O(n^2 \cdot 2^n)$ with bitmask DP
• Feasible for $n \leq 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.