Is showing a graph is non-Hamiltonian NP-Complete? 
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...
 A: 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!"
A: (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.
