Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.
Is there a good / quick / easy way to see that in fact finding a Hamiltonian path should be much harder than finding a Euler path?
Maybe the following perspective helps:
When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily combined to an Eulerian tour. The point is, none of your decision "how to walk across the graph" can actually be wrong. You will always succeed and never get stuck.
The situation with Hamiltonian paths is different. Again, you might want to construct a path by walking along edges of the graph. But this time you can really make bad decisions. This means you cannot continue the path, but not all vertices have been visited. What you can do is back-track. That means you revert some of your old decisions and continue along a different path. Essentially all algorithms that are known for the general problem rely on some way or the other on back-tracking, or trying out a large set of solutions. This, however, is characteristic for NP-complete problems.
So (simplified) bottom-line: Eulerian path requires no back-tracking, but Hamiltonian path does.
(Notice that it might be that P=NP and in this case a clever Hamiltonian path algorithm would exist.)
Another detail that may help your intuition is that an Euler cycle exists if and only if each vertex has even degree. A similar theorem exists for Euler paths. This follows from a fairly straightforward proof--basically, every time you visit a vertex, you must then leave it, so each "visit" takes two from the degree of the vertex. This doesn't explain why Hamiltonian path is difficult (which, of course, we don't even actually know), but it does help to explain why finding an Euler path is easy.
Victor Adamchik gives an OK explanation of the proof. Most graph theory/discrete math books will likely have a proof as well which you may find easier.
The other answers give some good intuition why such a simple proof doesn't seem to work for Hamilton cycles.
"Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?"
The assumptions in your question are not correct.
Note that we don't know that $\mathrm{HamPath}$ is not in $\mathsf{P}$! Someone someday might find a very clever characterization of $\mathrm{HamPath}$ (similar to the characterization of $\mathrm{EulerPath}$ as having even degrees) which would put it inside $\mathsf{P}$.
Most people believe that it is not in $\mathsf{P}$ but it is not proven. The arguments (not proof!) for why it is unlikely to be in $\mathsf{P}$ is the same as the arguments for $\mathsf{P} \neq \mathsf{NP}$ and most of them don't say much about $\mathrm{HamPath}$ itself other than the fact that it is $\mathsf{NP\text{-}complete}$.
Now, you may ask why $\mathrm{HamPath}$ is $\mathsf{NP\text{-}complete}$ but we can't show that $\mathsf{EulerPath}$ is $\mathsf{NP\text{-}complete}$? Because someone has find a characterization of it which is in $\mathsf{P}$ and then answer would be similar to why we believe that $\mathsf{P} \neq \mathsf{NP}$ so it is unlikely (but not proven!) that $\mathsf{EulerPath}$ is $\mathsf{NP\text{-}complete}$.
Here's one quick way of looking at it. The HAM-PATH problem is $\mathsf{NP}$-complete, so currently we do not if it can be solved in polynomial time or not. At least nobody has come up with such an algorithm. The Eulerian path problem on the other hand is provably in $\mathsf{P}$ since we have polynomial time algorithms for it. An $\mathsf{NP}$-complete problem such as HAM-PATH has resisted attacks so far, so this is one immediate way of seeing or believing it is harder than a problem in $\mathsf{P}$, say finding an Eulerian path.
