Circuit hamiltonien

Soit $G$ un graphe (orienté ou non), un circuit hamiltonien dans $G$ est un circuit passant par une et une seule fois par chaque sommet de $G$. Le problème du circuit hamiltonien est le suivant :

• données : un graphe $G$
• question : trouver un circuit hamiltonien dans $G$.

Ce problème est NP-Complet.