# Association between Hamiltonian and Eulerian graphs

I have a question, and also an answer which I assume, is correct, but would like to ask, if some of you could elaborate, and add validity to the provided claim or develop a discussion.

I did not find this question, nor the answer anywhere.

Question:

Is there any formal association or fundamental relationship, (as in some kind of theorem etc.) between Hamiltonian graphs and Eulerian graphs?

No such thing exist. Simple proof is, that finding a Hamiltonian path in a graph is NP-hard problem, and finding Eulerian path is not a NP-hard problem. Or in other words: If this statement is indeed true, finding the Eulerian path should also be NP-hard problem, which we know is not.

• "...finding the Eulerian path should also be NP-hard problem, which we know is not." implies $P \neq NP$ (which is not yet proved.) – Rebecca J. Stones Feb 8 '14 at 0:17
• Finding Eulerian path is not NP-hard.That is completely true. – Satoshi Feb 8 '14 at 0:18
• Do we agree EULERIAN PATH is in $P$? If $P=NP$, then $P=NP$-complete, and so every $P$ problem would be $NP$-hard. Therefore, if there exists a $P$ problem outside of $NP$-hard (as you're asserting), we must have $P \neq NP$. – Rebecca J. Stones Feb 8 '14 at 0:40