# 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 |