Is the longest Hamiltonian cycle NP-complete? As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I'm confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I'm looking at really is the longest?

Any help would be appreciated!
Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the decision version of that problem. 

Here, the decision version is: 


  Does the weighted graph $G$ have a Hamiltonian path with total weight at least $x$? 


For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least $x$. So, the decision version is in NP.



To understand why we look at the decision version, first note that NP is a class of decision problems, so only a decision problem can be NP-complete. (although we can construct an analogue of NP for optimisation problems, as in this answer). Solving the optimisation version also solves the decision version, so the optimisation version is at least as hard as the decision version. Since the theory gets easier when working with decision problems, focusing on the decision version is often helpful.