Euler and Hamiltonian Paths

← Back to Graph Theory

An Euler path visits every edge exactly once; a Hamiltonian path visits every vertex exactly once. Euler path existence is easily checked (all vertices have even degree), while Hamiltonian path is NP-Complete. This contrast illustrates the gap between polynomial and exponential problems.

mathematics-for-cs discrete-mathematics graph-theory euler hamiltonian