A Hamiltonian cycle is a cycle that contains all the tops of the graph.

There is no general algorithm (i.e. valid for any graph) and effective (i.e. no algorithm in the number of computational steps or a polynome the size of the graph) to find out if there is a Hamiltonian cycle in a graph.

**DIRAC Condition: If** for all the tops u of the graph G degree (u) 'n /2 then G contains a Hamiltonian cycle

**ORE Condition: If** for any pair u and v of non-neighbors deg(u) 'deg(v) 'then G contains a Hamiltorian cycle

If a graph verifies diraC's condition then it verifies the orE condition (the reciprocal is false).