Menemukan lintasan Hamilton tampaknya lebih mudah karena graf sering kali memiliki lebih banyak sisi daripada simpul, sehingga lebih sedikit syarat yang harus dipenuhi. Namun, tidak seorang pun mengetahui apakah hal ini benar. Belum diketahui adanya uji sederhana untuk menentukan apakah suatu graf memiliki lintasan Hamilton. Untuk graf kecil, hal ini bukan masalah, tetapi seiring bertambahnya ukuran graf, pemeriksaan keberadaan lintasan Hamilton menjadi semakin sulit. Bahkan, sejauh yang kita ketahui, pertanyaan ini merupakan contoh masalah yang secara umum terlalu sulit diselesaikan oleh komputer karena merupakan contoh masalah NP-lengkap.