グラフの同じ辺を２度は通らず，すべての頂点を巡ることのできる路をハミルトン路という．与えられたグラフに対し，ハミルトン閉路が存在するか否かを決定する一般的な規準をみつけることは，グラフ理論のなかでも最も難しい問題のひとつと考えられている．

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

［１］ハミルトン閉路をもたないグラフで，頂点をひとつ取り除いた部分グラフもハミルトン閉路をもつ最小のものはペテルセングラフである．ペテルセングラフは五角形とその内側にある星形五角形を結んだ形として描かれることが多い．

［２］４連結なグラフはいつでもハミルトン閉路をもつ

［３］３次正則３連結でかつハミルトン閉路をもたない，知られている平面グラフの最小次数は４６である．

［４］３次正則５辺連結でかつハミルトン閉路をもたない，知られている平面グラフの最小次数は４４である．

［５］単純凸多面体，すなわち，どの頂点次数も３のとき，頂点の数が２８以下であればハミルトン閉路をもつ（立方体，切頂八面体，正十二面体など）た

［６］単純多面体でかつハミルトン閉路をもつ，知られている多面体の最小頂点数は３８である．

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