Un cycle Hamiltonien est un cycle qui contient tous les sommets du graphe.
Il n’y a pas d’algorithme général (càd valable pour n’importe quel graphe) et efficace (càd pas d’algorithme dans le nombre d’étape de calcul soit un polynôme de la taille du graphe) pour trouver si il y a un cycle hamiltonien dans un graphe.
Condition de DIRAC : Si pour tous les sommets u du graphe G degré(u) >= n /2 alors G contient un cycle hamiltonien
Condition de ORE : Si pour toute paire u et v de non voisins deg(u) + deg(v) >=n alors G contient un cycle hamiltorien
Si un graphe vérifie la condition de DIRAC alors il vérifie la condition de ORE (la réciproque est fausse).