Известно, что он является NP-полным, чтобы проверить, существует ли гамильтонов цикл в 3-регулярном графе, даже если он плоский (Гэри, Джонсон и Тарьян, SIAM J. Comput. 1976) или двудольный (Akiyama, Nishizeki, и Saito, J. Inform. Proc. 1980), или чтобы проверить, существует ли гамильтонов цикл в...