組合せとグラフの理論(塩田)第9回 (2) クラトフスキーの定理

部分グラフの平面性との関係

 平面性の判定条件については、クラトフスキーの定理、という有名な定理があります。 まずは簡単な命題から。
Prop.8 $H$ をグラフ $G$ の部分グラフとする。このとき
  1. が平面的 $\Rightarrow$ も平面的。
  2. が非平面的 $\Rightarrow$ 非平面的。
には $G$ と $H$ のどちらが入るでしょうか。 答えは自分で考えてから

$K5$ と $K_{3,3}$

 さて、平面性の要(かなめ)となるのは、次の 2 つのグラフです。
$K_5$ $K_{3,3}$
Th.9 $K_5$ は非平面的である。
証明 頑張って辺の交差無く描いてみましょう。
  1. $K_5$ の部分グラフ $C_5$ はねじらずに描かねばなりません。
  2. 辺 $wz$ をこの5角形の内側に描く場合を考えます。(後の Th.14 より内側に描く場合のみ考えればよいことがわかります。)
  3. すると辺 $vx$, $vy$ は5角形の外側に描かざるを得ません
     または   またはその逆
  4. 残る 2 本の辺 $wy$, $xz$ は色付きの4角形の領域に描かざるを得ませんが、交差させずに描くことは不可能です。
(証明終)
Th.10 $K_{3,3}$ は非平面的である。
証明 Th.9 の証明と同様に、
ここまで描くと残る 2 本の辺 $vy$, $wz$ は6角形の内側に描かざるを得ず、 交差させずに描くことは不可能です。 (証明終)

クラトフスキーの定理

Th.11(クラトフスキー) グラフ $G$ について次は同値である。
  1. $G$ は平面的である。
  2. $G$ のいかなる部分グラフを縮約しても、$K_5$ や $K_{3,3}$ にはならない。
  3. $G$ のいかなる部分グラフも、$K_5$ や $K_{3,3}$ に位相同型ではない。
ただし位相同型とは、次の図のように次数 2 の部分を描き替えると同型になること。
  
証明はとても長いので省略します。
Ex.12 ペテルセングラフ は非平面的である。
クラトフスキーの定理を用いた証明は プリント の第1, 第2の証明を見てください。
Rem.13 Th.11 は定理としては美しいのですが、 「全ての部分グラフ」は膨大な個数存在しますのでプログラミングには使えません。 塩田のグラフ描画ツールでは計算量 $O(n^4)$ の平面性判定アルゴリズムを実装してあります ( $n$ は頂点数 )。