Proving Hamiltonian Cycle is NP Complete

A language is in NP if a proposed solution can be verified in polynomial time. In this case a proposed solution is simply a listing of the vertices in the order they appear in the claimed cycle. This list is the so-called certificate.

To check if this list is actually a solution to the Hamiltonian cycle problem, one counts the vertices to make sure they are all there, then checks that each is connected to the next by an edge, and that the last is connected to the first.

This takes time proportional to $n$, because there are $n$ vertices to count and $n$ edges to check. $n$ is a polynomial, so the check runs in polynomial time.

Note that this only shows that Hamiltonian Cycle is in NP, not that it is NP-complete.