---
tag: 090WPKFABX
kind: definition
name: Hamiltonian graph
msc: [05C45]
defines: 0HYV2NME07
uses: [0HKXNG2RS1]
sources:
  - url: https://en.wikipedia.org/wiki/Hamiltonian_path
    locator: Definitions
---

## Definition

A [[graph|0JD5C82QMB]] is Hamiltonian if it has a [[Hamiltonian cycle|0HKXNG2RS1]].

## Remarks

The [[cycle graph|0QQ0F12962]] $C_n$ and the [[complete graph|03WKB2H474]] $K_n$ for $n \ge 3$ are Hamiltonian.
A [[tree|0MJ0JS72DZ]] is not Hamiltonian, because it has no cycle.
The [[Petersen graph|0NR95CTFCZ]] is not Hamiltonian.
[[Dirac's theorem|0TC99BRSSB]] and [[Ore's theorem|0NACHJYPKW]] give sufficient conditions in terms of degrees.

## Explanations

### L1 human

A graph is Hamiltonian when you can visit all of its vertices in one round trip, each vertex once.
Many edges make this easier, and this is the idea of the theorems of Dirac and Ore.