leo valdez
leo valdez

Reputation: 259

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

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?

Upvotes: 0

Views: 1006

Answers (1)

Mauricio Irace
Mauricio Irace

Reputation: 41

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.

Upvotes: 3

Related Questions