Problem złożoności czasowej znajdowania rozwiązania problemu grafu hamiltonowskiego wiąże się z brakiem twierdzenia takiego jak twierdzenie Eulera dla grafów Eulera. Owo twierdzenie pozwala w czasie liniowym (tj. zależnym liniowo od, w tym przypadku, liczby wierzchołków) znaleźć odpowiedź na pytanie, czy graf jest eulerowski. W przypadku grafów Hamiltona twierdzenie takie prawdopodobnie nie istnieje.
Znalezienie algorytmu znajdowania drogi Hamiltona w czasie wielomianowym jest „Świętym Graalem” informatyki, i chociaż powstały już setki publikacji opisujących rzekomo taki właśnie algorytm, problem jest nadal otwarty. Według znakomitej części specjalistów taki algorytm nie istnieje („gdyż, zgodnie z rachunkiem prawdopodobieństwa, ktoś już by taki algorytm znalazł”), jednak do czasu udowodnienia, że takowy algorytm nie istnieje, lub udowodnienia, że taki dowód nie może zostać przeprowadzony, należy wstrzymać się z kategorycznymi osądami. thumb|Przykładowy cykl hamiltonowski w grafie Mycielskiego