[yarg]

It's not the travelling salesman - as per the description it's an unweighted graph.

This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.