タットグラフ

タットグラフは、46頂点、69辺からなる3-正則グラフであり、W・T・タットにちなんで名付けられた。頂点は3色で彩色可能、3-辺彩色可能であり、内周は4、半径は8である。
タットグラフは立方体グラフであり多面体グラフであが、ハミルトン路を持たない。したがって、テイト予想の反例である。
1946年にタットはこのテイト予想の反例としてこのグラフを公開した。そして後に、グリンベルクの定理などにより、他の反例も見つかった。
構成.
タットは、タットの小片（Tutte fragment）と呼ばれるより小さな構成要素を3つ組み合わせることで、ハミルトン路を持たない多面体グラフを更生した。この小片の飛び出たような辺は「強制的な」辺（＝ハミルトン路の一部に使わなければならない辺）であり、このへんを中心の頂点で3つ連結すると、ハミルトン路はその3つの辺の内2つしか通る事ができない。したがって、タットグラフはハミルトン路を持たない。
組み合わせたグラフは3-正則グラフであり、平面グラフである。したがって、シュタイニッツの定理より、対応する多面体が存在し、その多面体は25つの面を持つ。
この多面体は、四面体から3つの頂点を切り落とすことで幾何学的に実現することができる。4つの大きな面を含む9面からなり、4面のそのうち3つは小片の間に対応し、4つ目は外周に対応する。
代数的な性質.
タットグラフの自己同型群は Z/3Z であり、3つの元を持つ巡回群である。
タットグラフの固有多項式は
である。
関連するグラフ.
タットグラフは1946年に発見された3-正則グラフであり、最初にハミルトン路が存在しないことが知られたグラフであるが、そのような性質を持つグラフの中で最小のグラフではない。
1965年にレーダーバーグは38頂点の Barnette–Bosák–Lederberg グラフを発見した。1968年には、グリンベルクがテイト予想の反例として42、44、46頂点のグリンベルクグラフを追加した。1974年には、フォークナーとヤンガーは42頂点と44頂点の反例を発見した。
そして1988年に、ホルトンとマッケイは6種類の38頂点からなるハミルトン路を持たない多面体を見つけた。それらは五角柱の2つの頂点をタットの小片に置き換えたものからなる。