25.12. The Hamiltonian Cycle Problem — OpenDSA Complete Catalog

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.

Given a graph $G = (V,E)$, does the graph contain a Hamiltonian Cycle?

Does the graph below contain a Hamiltonian Cycle?

Yes

Does the graph below contain a Hamiltonian Cycle?

No

OpenDSA Complete Catalog