Oznaczenia Niech oznacza graf, zbiór jego wierzchołków, zbiór krawędzi, moc zbioru, pojedynczy (w tym przypadku -ty) wierzchołek grafu, a stopień wierzchołka (liczbę kończących się w nim krawędzi). Tradycyjnie oznacza się oraz zapis będący zbiorem dwuelementowym wierzchołków, używa się do oznaczenia krawędzi między i (w przypadku digrafów jest to para uporządkowana, gdyż liczy się kolejność oznaczająca kierunek krawędzi).
Indeksowanie wierzchołków Ścieżka/cykl Hamiltona może być jednoznacznie wyznaczona przez indeksowanie wierzchołków – tj. nadanie im indeksów, powiedzmy takich, że istnieje ścieżka Hamiltona przechodząca w takiej właśnie kolejności przez wierzchołki grafu.
Gdy znane jest indeksowanie wyznaczające ścieżkę Hamiltona, to znalezienie (lub potwierdzenie nieistnienia) cyklu Hamiltona jest trywialne i sprowadza się do sprawdzenia, czy istnieje krawędź – zajmuje to, w zależności od sposobu reprezentacji grafu, czas stały lub gdzie to liczba wierzchołków danego grafu (zobacz: Notacja dużego O).
Warunek konieczny Jeżeli graf jest hamiltonowski to dla każdego niepustego podzbioru zbioru wierzchołków zachodzi
gdzie oznacza liczbę spójnych składowych grafu