The decision problem:
Does this graph have a Hamilton Cycle?

is NP-Complete. That means that there is no known efficient procedure to decide whether or not a given graph has a Hamilton Cycle.
It's worth noting that given a solution to the Decision version of the Hamilton Cycle problem, we can, with only a polynomial amount of extra work, find an actual Hamilton cycle.
Informally, a Hamilton Cycle in a graph is a cycle that visits every vertex exactly once. Because it's a cycle it finishes where it started.

Slightly more formally, a Hamilton Cycle is a list of vertices from the graph such that:

Each vertex appear exactly once
For every $1{\le}i{\lt}n,$ $(v_i,v_{i+1})\in{E(G)}$

where we take $v_{n+1}=v_1$

For a given graph it's usually easy to find a Hamilton cycle, or easy to show that there is no Hamilton Cycle, but the problem of finding a Hamilton Cycle in a general or arbitrary graph has no known efficient procedure. It is NP-Complete.

(none)	(none)			CategoryTheory Euler FourColourTheorem MathematicsTaxonomy ThreeUtilitiesProblem
↓	↓		↓	↓
(none)			EulerCycle GraphTheory
			↓
		⇌	You are here HamiltonCycle
			↓
			NPComplete Polynomial
↓	↓		↓	↓
(none)	(none)			ComplexNumber FundamentalTheoremOfAlgebra RootsOfPolynomials ThisPageNeedsRevisiting

Local neighbourhood - D3

Last change to this page
Full Page history
Links to this page

Edit this page
(with sufficient authority)
Change password

Recent changes
All pages
Search

Hamilton Cycle

Navigation

You are here

Local neighbourhood - D3