Hamiltonovský graf jegraf, který lze projít takovou cestou, že každý jeho uzel je navštíven právě jednou s výjimkou uzlu výchozího, který je zároveň uzlem cílovým. Neboli – graf jehamiltonovský, právě když obsahuje kružnici, která prochází všemi jeho uzly (tzv.hamiltonovská kružnice). Název připomíná irského matematika a fyzikaW. R. Hamiltona (1805–1865), od kterého pocházel hlavolam, v němž bylo za úkol obejít po hranách vrcholy pravidelnéhodvanáctistěnu.
Ačkoliv se hamiltonovské grafy zdají být obdoboueulerovských grafů, rozhodnout, zda je grafhamiltonovský, není vždy snadné. Dosud totiž není známa žádná jednoduchá nutná a postačující podmínka k tomu, aby graf byl hamiltonovský. Je však známo několik postačujících podmínek k hamiltonovskosti grafu.
K tomu, aby byl graf su ≥ 3 uzly hamiltonovský, tedy stačí splnění některé z následujících podmínek:
 | Graf na obrázku nesplňuje Diracovu podmínku (obsahuje uzel 2.stupně, přičemž 2 < 5/2). Splňuje Oreho podmínku (součet stupňů libovolných dvou nespojených uzlů je alespoň 5). Je tedy podle výše uvedených podmínekhamiltonovský. Tento graf splňuje i Pósovu podmínku (počet uzlů stupně 1 je menší než 1, počet uzlů stupně 1 a 2 je menší než 2). |
 | Graf na obrázku nesplňuje Oreho podmínku (obsahuje nespojené uzly 2. a 3. stupně, přičemž 2+3 < 7) ani Diracovu podmínku. Splňuje Pósovu podmínku (počet uzlů 1. stupně je menší než 1, počet uzlů 1. a 2. stupně je menší než 3), a je tedy hamiltonovský. |
 | Graf na obrázku splňuje Diracovu podmínku, neboť každý jeho uzel má stupeň alespoň 3 a splňuje i podmínku Oreho, neboť každé dva uzly nespojené hranou mají součet stupňů alespoň 6. A konečně splňuje i Pósovu podmínku, neboť v něm nejsou žádné uzly stupně menšího než 3. |
Vteorii grafů jehamiltonovská kružnice (takéhamiltonovský cyklus)grafu takovákružnice v tomto grafu, která projde právě jednou všemi jehovrcholy. Graf, který obsahuje hamiltonskou kružnici, se nazývá Hamiltonovský graf.Hamiltonovská cesta je takovácesta v daném grafu, která prochází každým jeho vrcholem právě jednou.
Každý graf nemusí mít nutně hamiltonovskou kružnici. Nutnými (avšak nikoli postačujícími) podmínkami je, že graf musí býtsouvislý a každý vrchol musí mítstupeň nejméně rovný dvěma (ke každému vrcholu musí vést alespoň 2 hrany).
Problém nalezení hamiltonovské kružnice jeNP-úplný.
