I have read the definition on wikipedia and it says:

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

This definition does not say that this cycle should cover every vertex of the graph.

Till today I assumed that hamiltonian cycle should cover all the vertices But,today my teacher was reducing the hamiltonian cycle to Travelling salesman problem and he told that this condition is not necessary Can Anyone please let me know the correct definition as well as any source of it's definition.

  • 2
    $\begingroup$ "visits each vertex exactly once" does mean it covers all vertices, and additionally that it visits each only once $\endgroup$ – user160738 Nov 9 '15 at 19:41
  • 1
    $\begingroup$ It's right there in your quote: a Hamiltonian cycle is a Hamiltonian path, and a Hamiltonian path "visits each vertex exactly once." Perhaps you misunderstood your teacher. $\endgroup$ – TonyK Nov 10 '15 at 0:43

Yes, of course. Otherwise it's just a cycle (or circuit, as some would prefer to say.) The definition you quote does include this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.