ハミルトン閉路とは，任意の頂点から出発して，他のすべての頂点を１回だけ通って，元の頂点に戻れるグラフである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ペテルセン・グラフ

　ペテルセン・グラフは

［１］ハミルトン閉路でない

［２］どの頂点を取り除いてもハミルトン閉路となる

［３］１０個の頂点をもっている．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】タット・グラフ

　テイトは

［１］すべて次数３の頂点

［２］どの２つの頂点を取り除いても連結のまま

であるグラフは「ハミルトン閉路」であると予想したが，タット・グラフはその反例である．

　すなわち，

［１］４６個の頂点をもっていて，そのどれもが次数３

［２］どの２つの頂点を取り除いても連結のまま．

［３］ハミルトン閉路でない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】騎士の巡回

［Ｑ］８×８のチェス盤のマスすべてをナイト（騎士）で巡ることができるか？

　この問題はｎクイーン問題と並んで最もよく調べられている問題である．ハミルトン閉路を見つける問題の特殊な場合に相当する．

　８×８のチェス盤には１０^13通り以上の解があるが，意外にもひとつの解を見つけるのも簡単ではない．うまくいくとは限らないヒューリステッィク（経験則的）なアルゴリズムが知られているだけであるという．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝