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