グリンベルグの定理

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

ハミルトン閉路はグラフの全ての頂点を1度ずつ通る閉路である。ハミルトン閉路Cを持つ有限の平面グラフを考える。ジョルダンの閉曲線定理より、平面はCの「内側」と「外側」の2つの部分に分割される。グラフのどの面も2つの部分のどちらか一方に属する。内側と外側に属するk角形の面の数をそれぞれf_k, g_kとする。グリンベルグの定理によれば、 $${\displaystyle \sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0}$$ である。これはオイラーの多面体公式から容易に導出できる^[1]。

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

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

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

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

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

任意の3-正則2部多面体グラフがハミルトンであることを述べるバーネットの予想（英語版）の反例をグリンベルグの定理で求めることはできない。ハミルトン性に拘わらず任意の3-正則2部多面体グラフについてグリンベルグの定理の式を満たすように面を二分することができるためである^[7]。