クラトフスキーの定理の証明(2)点連結度から1-連結の証明まで

グラフ理論において、あるグラフが平面的であるかどうかを見極めるための重要な定理、

クラトフスキーの定理

の証明第2弾です。

まだ第1弾を読まれていない方は、まずそちらからご覧ください。

さて、今回からいよいよ証明の説明に入っていきます。

スポンサーリンク
レクタングル(大)広告

■ クラトフスキー部分グラフ

クラトフスキー部分グラフ とは、\(K_5\) や \(K_{3,3}\) の細分である部分グラフのことです。

クラトフスキー部分グラフ

■ 連結

グラフのどの2頂点も、いくつかの辺でつながっているとき、そのグラフは 連結 であるといいます。

連結であるグラフを 連結グラフ 、そうでないグラフは 非連結グラフ と呼びます。

非連結グラフ \(G\) は、いくつかの連結グラフ \(H_1,H_2,H_3,\cdots \) に分かれており、それらを \(G\) の 連結成分 といいます。

連結と非連結

■ 点連結度

グラフ \(G\) を非連結にするために、最小で何個の頂点を取り除かなければならないかを表す数値です。

点連結度が \(k\) 以上のグラフを k-連結グラフ といいます。

頂点を取り除くときは、その頂点に接続した辺も一緒に取り除きます。

また、ハミルトンサイクル(グラフのすべての頂点を1回ずつ通るサイクル)が存在するグラフの点連結度は2以上になります。

なぜなら、輪の形で並んだ頂点は、1個取り除いただけでは非連結にできないからです。

さらに、グラフの点連結度は、グラフの頂点の中で次数が最小である頂点の次数以下となります。

なぜなら、ある頂点に接続している辺をすべて取り除けば、その頂点が孤立するのは明らかだからです。

点連結度

■ 証明の流れ

クラトフスキーの定理を証明するためには、あらゆる非平面的グラフがクラトフスキー部分グラフを含むことを証明する必要があります。

しかし、実際は最小の非平面的グラフに対してのみこれを証明すれば十分です。

なぜなら、最小の非平面的グラフがクラトフスキー部分グラフを含んでいれば、

そうでない非平面的グラフも当然それを含むことになるからです。

証明の流れとしては、

□ まず、クラトフスキー部分グラフのない最小の非平面的グラフは、3-連結グラフであることを示します。
□ その後、クラトフスキー部分グラフのない3-連結グラフは平面的であることを示し、これはグラフが非平面的であることに矛盾することを導きます。(背理法)

■ 最小の非平面的グラフが 1-連結 であることの証明

□ 最小の非平面的グラフ \(G\) が 1-連結でない、すなわち非連結であると仮定します。

□ \(G\) の連結成分の1つを \(C\) とします。

□ \(G\) は最小の非平面的グラフなので、たとえ1つでも頂点や辺を取り除くと、平面的になります。

その結果、\(C\) も \(G-C\) も平面的となり、\(G\) 全体も平面に描くことができるので、

\(G\) が非平面的であることに矛盾します。

1-連結の証明

■ まとめ

今回の記事も、大部分を用語の説明に使ってしまいました。

お気づきの方もいるかもしれませんが、クラトフスキーの定理の証明は、

いくつもの従属命題の証明から成り立っています。

私が初めてこの定理を学んだとき、その証明の壮大さに感銘を受けました。

次回も分かりやすい解説に努めますので、引き続きよろしくお願いいたします。

次の記事 → クラトフスキーの定理の証明(3)誘導部分グラフから2-連結の証明

スポンサーリンク
レクタングル(大)広告
レクタングル(大)広告

シェアする

  • このエントリーをはてなブックマークに追加

フォローする