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

7k Views Asked by At

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.

3

There are 3 best solutions below

3
On BEST ANSWER

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

0
On

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.

0
On

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 https://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path