13.8 平面グラフの異なる特徴付け

本章で何度か \(K_{5}\) と \(K_{3,3}\) に触れた理由は「犬と quadrapus のパズルで応用できるから」だけではない。この二つのグラフは、本章で利用したものと異なる平面グラフの離散的な特徴付けで利用される。次の有名な結果が知られている:

定理 13.8.1[Kuratowskiクラトフスキー の定理 (Kuratowski's theorem)]

グラフは \(K_{5}\) または \(K_{3,3}\) をマイナーとして持つとき、かつそのときに限って平面グラフでない。

定義 13.8.2

グラフ \(G\) に対して「頂点の削除」「辺の削除」「隣接する二頂点の融合」を繰り返し適用1して得られるグラフを、\(G\)のマイナー (minor) と呼ぶ。

例えば図 \(\text{13.16}\) を見ると、\(C_{3}\) が \(\text{(a)}\) のグラフのマイナーだと分かる。実は、連結グラフは木でないとき、かつそのときに限って \(C_{3}\) をマイナーに持つ。

C_{3} が \text{(a)} のグラフのマイナーだと示す操作列の一例: 順に「e_{1} に隣接する二頂点を融合」「v_{1} と隣接する辺を削除」「v_{2} を削除」「e_{2} を削除」「v_{3} を削除」が適用されている。
図 13.16\(C_{3}\) が \(\text{(a)}\) のグラフのマイナーだと示す操作列の一例: 順に「\(e_{1}\) に隣接する二頂点を融合」「\(v_{1}\) と隣接する辺を削除」「\(v_{2}\) を削除」「\(e_{2}\) を削除」「\(v_{3}\) を削除」が適用されている。

定理 13.8.1 の既知の証明は入門書に含めるには少し長すぎるので、ここでは省略する。

  1. それぞれの操作の回数と適用順序に制限はない。 ↩︎

広告