多面体グラフ
P. G. テイトは「3次の多面体グラフはハミルトン路を持つ」というテイト予想 (グラフ理論)を1884年に提唱したが、この予想1946年にはW. T. Tutteによってタットグラフと呼ばれるハミルトン路を持たない多面体グラフはにより反証された。更に、4次以下の多面体グラフと言う条件ならばより小さな11頂点・18辺からなるハーシェルグラフ、4次以上の頂点を含むが、面が三角形のみである多面体グラフならば11頂点27辺からなるゴールドナー・ハラリーグラフがハミルトン路を持たないグラフとして知られている。
より強い主張として、ある α < 1 (shortness exponent)に対し最長の道が無限個の多面体グラフが存在し、頂点数 n に対してO(n)個ある。
Duijvestijnは多面体グラフの種類を26辺からなるものまで数え上げた。6、7、8辺からなる多面体グラフの数は、
1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sequence オンライン整数列大辞典の数列 A002840.
また、頂点数別に多面体グラフを数え上げると、4、5、6頂点からなる多面体グラフの数は、
1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (sequence オンライン整数列大辞典の数列 A000944.