Reputation: 259
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
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