# 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