クラトフスキーの定理の証明(5)3-連結は平面的を証明する準備

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

クラトフスキーの定理

の証明第5弾です。

前回までの記事を読まれていない方は、まずそちらからご覧ください。

前回までの説明で、クラトフスキー部分グラフを含まない最小の非平面的グラフが 3-連結であることを示しました。

次に、そのようなグラフは平面的グラフになってしまうことを証明するのですが、

その準備として、2つの従属命題を証明します。

今回は、その続きです。

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

■ 縮約によってクラトフスキー部分グラフが生じないことの証明(続き)

□ グラフ \(G\) の中の辺 \(e\) を縮約して得られたグラフを \(G_e\)、縮約してできた頂点を \(v_e\) とします。

□ もし、\(v_e\) がクラトフスキー部分グラフ \(H\) の頂点にあたる場合、

\(v_e\) から辺を奪わずに拡逆すると、\(H\) が \(G\) の部分グラフとなって矛盾するのは明らかです。

縮約とクラトフスキー部分グラフ3

□ したがって、複製された頂点が \(v_e\) から辺を奪って拡逆する場合を考えますが、

いずれのパターンでも、やはり \(H\) が \(G\) の部分グラフとなって矛盾してしまいます。

□ ここで、そのすべてのパターンを解説すると、説明が長くなってしまうので割愛しますが、

結論だけ書いておくと、

1. \(K_5\) において 1辺を奪って拡逆 → \(G\) が \(K_5\) の細分を含む
2. \(K_5\) において 2辺を奪って拡逆 → \(G\) が \(K_{3,3}\) を含む
3. \(K_5\) において 3辺を奪って拡逆 → \(G\) が \(K_5\) の細分を含む
4. \(K_5\) において 4辺を奪って拡逆 → \(G\) が \(K_5\) を含む
5. \(K_{3,3}\) において 1辺を奪って拡逆 → \(G\) が \(K_{3,3}\) の細分を含む
6. \(K_{3,3}\) において 2辺を奪って拡逆 → \(G\) が \(K_{3,3}\) の細分を含む
7. \(K_{3,3}\) において 3辺を奪って拡逆 → \(G\) が \(K_{3,3}\) を含む

となります。

参考までに、1. と 2. のパターンについて、図を載せておきます。

縮約とクラトフスキー部分グラフ4


縮約とクラトフスキー部分グラフ5

■ 3-連結グラフを縮約しても 3-連結になることの証明

\(G\) を位数 5 以上の 3-連結グラフとする。その時、縮約しても 3-連結になるような辺 \(e\) が存在する。

□ \(G\) は位数 5 以上の 3-連結グラフで、\(G\) のいかなる辺を縮約しても 3-連結にならないものとします。

□ \(G\) の中の辺 \(e\) を縮約して得られたグラフを \(G_e\)、縮約してできた頂点を \(v_e\) とします。

□ \(G_e\) は 3-連結ではないので、\(v_e\) と \(z_e\) を取り除くことで

\(G_e\) が非連結になるような \(z_e\) が存在します。

このことは、辺 \(e\) の端点を \(x,y\) とすると、\(G\) が \(x\) と \(y\) と \(z_e\) を取り除くことで非連結になるということです。

縮約と3-連結1

□ \(x,y,z_e\) の3点で \(G\) を非連結にしたとき、連結成分 \(C\) のサイズ(辺の数)が最大になるように \(x,y\) を選びます。

この時、もう1つの連結成分は \(C’\) とします。

□ \(z_e\) と \(C’\) 上の頂点 \(u\) をつなぐ辺を \(f\) とします。

縮約と3-連結2

□ 仮定より、\(G\) から \(z_e,u,z_f\) の3点を取り除いたとき、

\(G\) が非連結になるような \(z_f\) が存在します。

なぜなら、そのような \(z_f\) が存在しないと、辺 \(f\) を縮約したとき、

グラフが 3-連結になってしまうからです。

□ \(C\) と \(x,y\) の誘導部分グラフは連結で、仮にこの部分グラフが \(z_f\) を

含んでいた場合、\(z_f\) を削除しても部分グラフを非連結にすることはできません。

もし、非連結になるなら、\(G\) から \(z_e,z_f\) の2点を削除しても非連結になり、

\(G\) が3連結であることに矛盾するからです。

□ したがって、\(z_f\) は \(C’\) に含まれていることになりますが、その場合、

\(z_e,u,z_f\) を削除してできた非連結グラフは、\(C\) よりも大きな連結成分を持つ

ことになり、\(C\) のサイズが最大であるという仮定に矛盾するわけです。

■ まとめ

この辺の証明は内容が難しく、読者に説明がうまく伝わっているか不安です。

記事の中で分からない部分があれば、コメント欄から遠慮なくご質問ください。

今回の記事では、クラトフスキー部分グラフを拡逆しても、やはりクラトフスキー部分グラフになることを、

あらゆるパターンで確認するのが大変でした。

この事実は、

縮約するとクラトフスキー部分グラフになるようなグラフは非平面的グラフである(ワグナーの定理

につながっているのかもしれません。

クラトフスキーの定理の証明も、ようやく出口が見えてきました。

最後までお付き合いいただければ幸いです。

次の記事 → クラトフスキーの定理の証明(6)3-連結は凸埋め込みを持つ証明

関連コンテンツユニット
スポンサーリンク
レクタングル(大)広告
レクタングル(大)広告

シェアする

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

フォローする

コメント

  1. 石井 より:

    Zfとは、最後の図ではどの部分を表していますか?

    • cue より:

      > 石井さん
      コメントありがとうございます。
      ご質問をいただき、英語の証明をもう一度読み直しました。
      Zfの位置があいまいになっていたので、記事を修正いたしました。
      お手数ですが、改めて記事をお読みいただければと存じます。
      石井さんのおかげで、僕も証明をより深く理解できました。
      感謝いたします。