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...

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!"
