Hamiltonian path- can I cover an edge twice when every vertex can be covered only once?

Question

From this question- Difference between hamiltonian path and euler path, every Hamiltonian path is not a Euler path. How can I cover every vertex exactly once and cross an edge twice?

I think you misread the answer in the referenced answer: it is not claimed that you could cross an edge twice in a Hamilton graph. No, it says: *"In a Hamiltonian path you may not pass through all edges."* ("may" in the sense of "might") — trincot, Sep 23 '18 at 21:07

score 3 · Answer 1 · answered Sep 23 '18 at 20:26

You can actually cover all the vertices without crossing every edge, for example, to cover all K4 (complete graph of 4 vertices) you only need to cross 3 edges. But it has 3 * (3+ 1)/ 2 = 6 edges. Even more: each node has degree 3, so it doesn't have an eulerian path, neither a circuit.

Hamiltonian path- can I cover an edge twice when every vertex can be covered only once?

1 Answers1