Hamiltonian graph

A graph $G$ is Hamiltonian if it has a Hamiltonian cycle.

A useful condition both necessary and sufficient for a graph to be Hamiltonian is not known. Ore’s theorem and the Bondy and Chvátal theorem give sufficient conditions, while a necessary condition follows quickly from the definition, namely:

Let $G=(V,E)$ be a graph of order at least 3. If $G$ is Hamiltonian, then for every proper subset $U$ of $V$, the subgraph induced by $V-U$ has at most $|U|$ components.

Title	Hamiltonian graph
Canonical name	HamiltonianGraph
Date of creation	2013-03-22 11:52:43
Last modified on	2013-03-22 11:52:43
Owner	drini (3)
Last modified by	drini (3)
Numerical id	13
Author	drini (3)
Entry type	Definition
Classification	msc 05C45
Classification	msc 55-00
Classification	msc 82-00
Classification	msc 83-00
Classification	msc 81-00
Synonym	Hamiltonian
Related topic	HamiltonianCycle
Related topic	HamiltonianPath
Related topic	OresTheorem
Related topic	BondyAndChvatalTheorem
Related topic	PetersensGraph
Related topic	Traceable