グリンベルグの定理

グリンベルグの定理（グリンベルグのていり、）は平面グラフがハミルトン閉路を持つ必要条件について述べた定理である。の反例など、特定のグラフの非ハミルトン性を証明するために広く用いられる。

名称は1968年に定理を証明したラトヴィヤの数学者の名に因む。

定式化 平面グラフはユークリッド平面上で辺を交差させることなく描いたグラフである。頂点と辺、そして無限面を含む面から構成される。頂点辺から成る面は角形となる。

ハミルトン閉路はグラフの全ての頂点を1度ずつ通る閉路である。ハミルトン閉路を持つ有限の平面グラフを考える。ジョルダンの閉曲線定理より、平面はの「内側」と「外側」の2つの部分に分割される。グラフのどの面も2つの部分のどちらか一方に属する。内側と外側に属する角形の面の数をそれぞれとする。グリンベルグの定理によれば、

である。これはオイラーの多面体公式から容易に導出できる。

この定理の系として、辺の数が3を法として2に合同でない面をただ1つ持ち、他の全ての面の辺数は3を法として2に合同である平面グラフは非ハミルトンであることが証明できる。後者の面ではが3の倍数となるので、総和は3の倍数でない、特に0でない。したがってグリンベルグの定理の述べる条件を満たさず、グラフはハミルトン閉路を持たない。例えば冒頭に示した図について、有限面は5または8角形だが、無限面のみ9角形であるのでグリンベルグの定理よりハミルトン閉路を持たない。

応用 グリンベルクスは定理を用いて が高い非ハミルトン3-正則多面体グラフを求めた。グラフの は、除去すると閉路を持つ複数のが構成される辺の数の最小値である。46頂点のタットグラフ、およびその派生物であるより小さな非ハミルトン3-正則多面体グラフの は3である。グリンベルクスは が4で44頂点24面の非ハミルトン3-正則多面体グラフ、 が5で46頂点25面の非ハミルトン3-正則多面体グラフ（冒頭図のグラフ）を発見した。

グリンベルグの定理は平面の捜索にも使用される。亜ハミルトングラフとはハミルトンではないが任意頂点1つを除けばハミルトンになるグラフである。1つの面を除く全ての面の辺の数が3を法として2に合同となるようにして構成できる。 は定理を用いてやや複雑な方法で平面3-正則亜ハミルトングラフを構成した。4角形の面が4つの7角形の面に隣接しており、他の面はすべて5または8角形のグラフであった。グリンベルグの定理の式を満たすためには4, 7角形である5つの面のうちの1面が他の4面から離れていればよいが、そのようなグラフは存在しない。

グリンベルグの定理はのような特定の非平面的グラフのハミルトン閉路の分析にも応用される。グラフの大きな平面的部分グラフを求め、グリンベルグの定理で部分グラフの非ハミルトン性を示し、どのハミルトン閉路も部分グラフに含まれない残りの辺の一部を通る必要があることを証明できる。

制約 グリンベルグの定理はハミルトン閉路が存在する必要十分を述べることができるのみで、例えば5, 8角形の面から成る平面非ハミルトングラフが存在する。定理の式が成り立つグラフではグリンベルグの定理を用いてハミルトンであるか否かを判定することはできない。

任意の3-正則2部多面体グラフがハミルトンであることを述べるの反例をグリンベルグの定理で求めることはできない。ハミルトン性に拘わらず任意の3-正則2部多面体グラフについてグリンベルグの定理の式を満たすように面を二分することができるためである。

脚注

注釈

出典

参考文献

; Dainis Zeps により英訳されている 。

外部リンク