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

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

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

　ペテルセン・グラフは

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

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

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

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

【２】タット・グラフ

　テイトは

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

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

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

　すなわち，

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

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

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

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