グラフの同じ辺を２度は通らずにすべての頂点をめぐることのできる路をハミルトン路という。

　与えられたグラフに対して、ハミルトン閉路が存在するか否かを決定する一般的な基準をみつけることはグラフ理論の中でも最も難しい問題であると考えられている。

　どの頂点も次数が３の凸多面体を単純多面体という。頂点数28以下の単純多面体はハミルトン閉路をもつ。

　一方、単純多面体でハミルトン閉路を持たないことが知られている最小の頂点数は３８である。

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

　ペテルセングラフはハミルトン閉路をもたないグラフで、頂点を一つ取り除いたどの部分グラフもハミルトン閉路を持つようなグラフの中で、最小次数１０のものである。

　４連結な平面グラフは常にハミルトン閉路をもつ。

　3次正則・５辺連結で、かつ、ハミルトン閉路を持たない、知られている最小の平面グラフの次数は４４である。

　3次正則・３連結で、かつ、ハミルトン閉路を持たない、知られている最小の平面グラフの次数は４６である。

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