クラトフスキーの定理の証明（6）3-連結は凸埋め込みを持つ証明

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

クラトフスキーの定理

の証明第6弾です。

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

前回と前々回の記事では、

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

\(G\) をクラトフスキー部分グラフを持たないグラフとする。その時、\(G\) のいかなる辺を縮約してもクラトフスキー部分グラフは生じない。

という2つの従属命題を証明しました。

今回はその従属命題を用いて、いよいよクラトフスキーの定理の証明を完結させていこうと思います。

■ 凸多角形

凸多角形 とは、どの 2頂点を結ぶ線分も、その多角形の外に出ることがないようなものです。

凸多角形では、どの内角の大きさも \(180^\circ\) 未満になっています。

平面的グラフ \(G\) の 凸埋め込み とは、すべての辺がまっすぐな線分で、

一番外側を除くすべての面が凸多角形であるような平面グラフです。

\(G\) をクラトフスキー部分グラフを含まない 3-連結グラフとする。
その時、\(G\) は凸埋め込みを持つ。

これは、\(G\) が平面的であることを示し、こうしてクラトフスキーの定理の証明が完結します。

上の命題を頂点数についての帰納法で証明します。

最小の 3-連結グラフは 4個の頂点を持ちます。

□ \(k\) を4以上の自然数、頂点数 \(|V|=k\) のクラトフスキー部分グラフを含まない 3-連結グラフを \(G_k\) とします。

□ 従属命題 A より、\(|V|=k+1\) のとき、縮約しても 3-連結になるような辺 \(e\) が存在します。

□ 従属命題 B より、クラトフスキー部分グラフを拡逆しても、クラトフスキー部分グラフを含まないグラフは生成できません。

以上のことから、\(G_{k+1}\) は \(G_k\) を拡逆して生成可能であることが分かります。

□ \(G_k\) が平面的であるとき、\(G_{k+1}\) も平面的であるかどうかを調べていきます。

□ \(G_k\) において、拡逆を行う頂点を \(z\) とします。

□ \(G_k\) は 3-連結なので、\(z\) を取り除くと 2-連結となり、

\(z\) は多角形の中に存在することになります。

□ \(z\) を拡逆したとき、複製元となる頂点を \(x\)、複製先となる頂点を \(y\) とします。

□ また、\(x\) に隣接した多角形上の頂点を \(x_1,\cdots,x_n\)、\(y\) に隣接した頂点を \(y_1,\cdots,y_n\) とします。

まだ帰納法の途中ですが、記事が長くなってきたので続きは次回にしたいと思います。

ここまで6回にわたり連載してきたクラトフスキーの定理の証明もいよいよ最終回。

クラトフスキー部分グラフを含まない 3-連結グラフは凸埋め込みを持つ（＝平面的である）ことを示し、

非平面的グラフを生成するには、やはりクラトフスキー部分グラフを含めなければならないという結論を導きます。

読者と一緒に感動の結末を迎えたいので、次回の記事もどうぞよろしくお願いいたします。