Ein Graph ist ein Eulerscher Graph, wenn es einen geschlossenen Kantenzug gibt, der jede Kante genau einmal enthält. Er ist ein Hamiltonscher Graph, wenn es einen Kreis gibt, der jede Ecke genau einmal enthält. Es ist sehr einfach zu prüfen, ob ein Graph Eulersch ist, und in diesem Fall lässt sich eine Eulersche Tour sehr leicht konstruieren. Dagegen gibt es für Hamiltonsch zwar ein paar einfache Kriterien und Verfahren, aber kein effizientes Verfahren, das für jeden Graphen funktioniert.