Гамильтонов путь: если есть путь для посещения каждой вершины графа ровно один раз. Самый длинный путь: учитывая граф G = (V, E) и целое число k, решите, существует ли простой путь длины k. В моем классе решение состоит в том, чтобы установить k = V-1, и тогда тривиально, что эти две проблемы эквивалентны. Я могу понять направление от Гамильтонова Пути до самого длинного пути. Но я не могу понять направление от самого длинного пути к гамильтонову пути, поскольку данное число k не обязательно должно быть числом вершин - 1.