# Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path can also be deduced by recursively traversing dfs.

• How do you solve Hamiltonian path using a DFS? – adrianN Jun 24 '16 at 12:24
• geeksforgeeks.org/find-paths-given-source-destination ..... Use it and check whether the path covers all vertices. – Ulsa Minor Jun 24 '16 at 12:26
• @UlsaMinor And what if it doesn't cover all the vertices? – David Richerby Jun 24 '16 at 12:29
• then their is no hamiltonian path available! – Ulsa Minor Jun 24 '16 at 12:32
• @UslaMinor But maybe there is another path that covers all the vertices? You've checked only one possible path. – Tom van der Zanden Jun 27 '16 at 7:45

Indeed, it's not even obvious that you can solve Hamiltonian path using depth-first search. Consider the graph that is a clique plus one extra vertex, which sends one edge to the clique, say to vertex $x$. If you start your depth-first search at $x$, none of the paths explored by the DFS will be Hamiltonian. Further, if you start at any other vertex in the clique, you might have to explore something like $n!$ paths before you find a path that visits every vertex in the clique, finishing at $x$ and then moves to the extra vertex.