# Questions on Graph and Hamiltonian [closed]

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.

## closed as unclear what you're asking by Nicholas Mancuso, Tom van der Zanden, Rick Decker, David Richerby, Wandering LogicFeb 17 '15 at 23:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Well, how did you infer it, and what part of the inference in specific are you unsure about? – Tom van der Zanden Feb 17 '15 at 19:45
• Dear @TomvanderZanden, i'm not sure, if a question is open (specially not a hamilton graph), can we say NP or NP-complete or ? and then would you please correct me? – M. holi Feb 17 '15 at 19:48
• @M.holi When someone says something is an "open" problem, that means that no one knows the answer yet. – apnorton Feb 18 '15 at 0:33
• Dear @anorton, can we say No-Hamiltonian is in NP Class? – M. holi Feb 18 '15 at 6:35

• @M.holi I suggest you go over your basics. Make sure that you understand what NP and coNP are, and what NP-hard and coNP-hard mean. NP and coNP are not the same. The language $L$ consisting of all Hamiltonian graphs is NP but probably not coNP – we don't know for sure, but since we believe that NP≠coNP, and $L$ is NP-complete, then it must be the case that $L$ is not in coNP. – Yuval Filmus Feb 18 '15 at 15:36