Megállapítható valahogyan, hogyha adott egy gráf, és kijelölünk rajta valamennyi élt, hogy azokon az éleken húzható Hamilton-kör?

Persze. A kijelölt élek által meghatározott részgráf pontjainak véges sok permutációja van, azokat végig nézve egészen biztosan kiderül, hogy van-e Hamilton-kör.

Gondolom, ez az algoritmus javítható exponenciális idejűre valahogyan, és amennyire én tudom, a probléma polinomidejű eldöntése még megoldatlan feladat. (Szóval egyelőre nincs ilyen, és nem is valószínű, hogy lesz.)

Ezenkívül vannak „gyorstesztek”, amik gyorsan cáfolják/bizonyítják a Hamilton-kör létét, de ezek csak speciális esetekben működnek (például a Pósa-tétel, vagy bizonyos összefüggőséggel kapcsolatos kritériumok).