クラトフスキーの定理

グラフ理論において、クラトフスキーの定理は、平面グラフの数学的禁制グラフ特性であり、カジミエシュ・クラトフスキーにちなんで名付けられました。これは、有限グラフが平面であるためには、( 5つの頂点を持つ完全グラフ) または( 6 つの頂点を持つ完全二部グラフで、そのうち 3 つが他の 3 つの頂点のそれぞれに接続されているもの。ユーティリティ グラフとも呼ばれる) の細分であるサブグラフを含まないことを規定しています。 ${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$

平面グラフは、頂点がユークリッド平面上の点で表され、辺が端点を表す点を結ぶ同一平面上の単純な曲線で表され、共通の端点以外で 2 つの曲線が交差しないグラフです。平面グラフは辺を表す直線セグメントで描かれることが多いですが、ファリの定理により、これはグラフ理論的特徴付けに何ら影響を及ぼしません。

グラフの細分化は、グラフの辺を 1 つ以上の辺のパスに細分化することによって形成されるグラフです。クラトフスキーの定理によれば、またはの辺を細分化して、さらに辺と頂点を追加して と同型のグラフを形成することが不可能な場合、有限グラフは平面グラフになります。同様に、有限グラフが平面グラフであるためには、またはに同相なサブグラフが含まれません。 ${\displaystyle G}$${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle G}$${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$

がグラフであり、そのグラフがまたは の細分であるサブグラフを含む場合、 は のクラトフスキーサブグラフと呼ばれます。^[1] この表記法を使用すると、クラトフスキーの定理を簡潔に表現できます。グラフが平面であるためには、クラトフスキーサブグラフが存在しない必要があります。 ${\displaystyle G}$${\displaystyle H}$${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle H}$${\displaystyle G}$

2 つのグラフと は非平面グラフであり、これはケース分析またはオイラーの公式を含む議論によって示されます。さらに、グラフを細分化しても非平面グラフを平面グラフにすることはできません。グラフの細分化が平面描画を持つ場合、細分化のパスはそのグラフ自体のエッジを表すために使用できる曲線を形成します。したがって、クラトフスキー サブグラフを含むグラフは平面グラフにはなり得ません。クラトフスキーの定理を証明する上でより難しい方向は、グラフが非平面である場合、必ずクラトフスキー サブグラフを含むことを示すことです。 ${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle G}$${\displaystyle G}$

非平面グラフのクラトフスキー部分グラフは、入力グラフのサイズに応じて線形時間で見つけることができます。 ^{[2]これにより、与えられた部分グラフがクラトフスキー部分グラフであるかどうかをテストするのが簡単なので、非平面入力に対して}平面性テストアルゴリズムの正しさを検証できます。^[3] 通常、非平面グラフには多数のクラトフスキー部分グラフが含まれます。これらの部分グラフの抽出は、たとえば交差最小化のための分岐およびカットアルゴリズムで必要です。合計サイズに依存した時間で多数のクラトフスキー部分グラフを抽出することが可能です。^[4]

カジミエシュ・クラトフスキは1930年に定理を発表しました。 ^[5]この定理は、同じく1930年にオーリン・フリンクとポール・スミスによって独立に証明されましたが、 ^{[6]彼らの証明は公表されませんでした。}立方平面グラフの特殊なケース（唯一の極小禁制部分グラフが である）も、 1930年にカール・メンガーによって独立に証明されました。 ^[7] それ以来、この定理の新しい証明がいくつか発見されました。^[8]${\displaystyle K_{3,3}}$

ソ連では、クラトフスキーの定理はポントリャーギン-クラトフスキーの定理、あるいはクラトフスキー-ポントリャーギンの定理として知られていました。 ^[9]この定理は1927年頃にレフ・ポントリャーギン によって独立に証明されたと伝えられています。 ^[10]しかし、ポントリャーギンは証明を公表しなかったため、 この用法は他の場所に広まっていません。^[11]

これに密接に関連する結果であるワグナーの定理は、同じ2つの禁制グラフとに関して、平面グラフをそのマイナーによって特徴付ける。すべてのクラトフスキー部分グラフは同じタイプのマイナーの特殊なケースであり、逆は真ではないが、これら2つの禁制マイナーのいずれかから（いずれかのタイプの）クラトフスキー部分グラフを見つけることは難しくない。したがって、これら2つの定理は同等である。^[12]${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$

拡張としてはロバートソン・シーモア定理がある。

• ケルマンス・シーモア予想は、5連結非平面グラフには${\displaystyle K_{5}}$