Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle? [duplicate]

Question

This question already has an answer here:

• Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is? 4 answers

To find a Hamilton cycle is a NPC problem, but Euler is not. Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information which originally edge does.

What properties make the Euler graph more easily to be resolved?

For example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation.

Answer 1

Suppose you are trying to find a Hamiltonian cycle on a graph.

You can solve this efficiently in the manner you describe (i.e. converting vertices into edges and then solving for an Euler path) if and only if the graph is a line graph.

There are a number of characterisations of line graphs.

For example, a graph is a line graph if and only if it does not contain any of these 9 graphs below as a subgraph:

An alternative characterisation is that a graph is a line graph if and only if you can partition the graph into cliques such that every vertex belongs to exactly two cliques.

This characterisation is perhaps more useful as you can apply Euler's proof to these cliques.

Answer 2

Euler proved the that a connected graph has a closed path traversing every edge if every vertex is of even degree, and he proved that a connected digraph has a closed path traversing every edge if every vertex has in-degree equalling out-degree. He gave an explicit construction in both cases. The construction can be easily systematized. Others have sped the algorithm up.