Is showing a graph is non-Hamiltonian NP-Complete?

Question

Show that graph is not Hamiltonian. Is this an NP-complete problem?

My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle than there is a path that can be traced with DFS that covers all vertices and comes back to the original source. Right?

I am not exactly sure though. Maybe my assumption is stupid! I just started to read on NP-complete problems. Need your help here...

Answer 1

You probably know that showing a graph is Hamiltonian is an NP-complete problem. Thus, showing that a graph is not Hamiltonian is a co-NP-complete problem. It is an open problem as to whether or not a co-NP-complete problem can also be NP-complete.

So, the short answer is, "we don't know yet!"

Answer 2

(This answer is wrong but by virtue of apnortons comment below it might yet prove instructional to someone else but me)

I'm a bit in doubt after reading the authorative answer by apnorton, but it seems to me the NP-completeness of (is-not-Hamiltonian) can still be proven. For this one would need to a) show that (is-not-Hamiltonian) is in NP and b) find a polynomial time reduction of (is-Hamiltonian) or another NP-complete problem to (is-not-Hamiltonian).

The first property can be proven by demonstrating a verifier for the problem, i.e. a deterministic Turing machine that accepts or rejects a given candidate solution in polynomial time. It's a bit of handwaving, but I'd imagine this can be constructed analogously to a verifier for (is-Hamiltonian).

The second property can be demonstrated by showing that $\neg$ (is-Hamiltonian) is equivalent to (is-not-Hamiltonian) $\cup$ (syntactically incorrect graph encodings). Assuming there exist polynomial time syntactical validation procedures for graph encodings, this constitutes a polynomial time reduction and so (is-not-Hamiltionian) would be NP-complete.