What is the difference between a Hamiltonian Path and a Hamiltonian Cycle?

$\begingroup$

The title says it all. I've seen confusing definitions of this, and would appreciate if someone can succinctly clear this up with definitions and examples.

$\endgroup$ 2

3 Answers

$\begingroup$

The cycle starts and ends in the same vertex, but the path does not.

$\endgroup$ 3 $\begingroup$

Hamiltonian cycle = a cycle (path ending in the same vertex it starts) that visits every vertex ($ n $ edges);
Hamiltonian path= a path that visits every vertex ($ n - 1 $ edges).

In the graph represented by the matrix of adiacence:

01001
10100
01010
00101
10010

We have 1 - 2 - 3 - 4 - 5 or 1 - 5 - 4 - 3 - 2 Hamiltonian paths. Also, 1 - 2 - 3 - 4 - 5 - 1 is a Hamiltonian cycle.

$\endgroup$ $\begingroup$

Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once Hamiltonian cycle is a Hamiltonian path that is a cycle, and a cycle is closed trail in which the “first vertex = last vertex” is the only vertex that is repeated.
For more info

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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