Is Non-hamiltonian cycle problem not in NP ? Since to verify it, we need to go through all possible paths which make it exponential in nature.
Please support your claim with credible links. I found over web that at lot of places it is written "The Non-hamiltonian cycle problem is not known to be in NP" --