This slideshow introduces and explains the "Hamiltonian Cycle" Problem.
We start with some definitions and background.
Hamiltonian Cycle is a graph cycle in an undirected or adirected graph that passes through each vertex exactly once.
For example - The edges marked in red in the graph below forms a Hamiltonian Cycle.
1
2
3
4
5
6
Given a graph G=(V,E), does the graph contain a Hamiltonian Cycle?
Does the graph below contain a Hamiltonian Cycle?
1
2
3
4
5
6
7
8
Yes
Does the graph below contain a Hamiltonian Cycle?
No
