Questions on Graph and Hamiltonian From this book and other study in complexity theory, I have seen the following statement:


  The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?


However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?


  Determining a that a Graph is not Hamiltonian is an NP-Complete problem.
No, determining whether a graph is not Hamiltonian is coNP-complete, and it is believed not to be NP-complete, indeed not in NP. Determining what a graph is Hamiltonian is NP-complete.