平面グラフとオイラーの定理の応用

平面的グラフとは

頂点以外の点で辺が交差しないように平面に書けるようなグラフを平面的グラフといいます。交差しないように実際に書いたものを平面グラフといいます。

なお，グラフ理論では平面に「書く」と言わずに 「埋め込む」と言うので，以下でも「埋め込む」という言葉を使います。

例えば，完全グラフ $K_4$ は左上図のように埋め込むと頂点以外で交差してしまっていますが，工夫すれば右上図のように交差なしで埋め込むことができるので平面的グラフです。

同様に，完全二部グラフ $K_{3,2}$ も左下図ではダメですが，右下図のように交差なしで埋め込めるので平面的グラフであることが分かります。

※完全グラフ，完全二部グラフ，連結などの意味が分からない方はグラフ理論の基礎の下の方を参照してください。

この記事の目標は $K_5$，$K_{3,3}$ が平面的グラフでないことを証明することです。$K_5$ や $K_{3,3}$ はどう頑張っても平面に交差なしで埋め込めないのです！

オイラーの定理

$K_5$ や $K_{3,3}$ が平面的グラフでないことを証明するためにオイラーの定理を用います。

例えば，さきほどの $K_4$ の例（右上図）では $v=4,e=6,f=4$ となりオイラーの定理が成立しています。

証明は，空間図形（凸多面体）におけるオイラーの多面体定理と同様です。オイラーの多面体定理の意味と証明のstep2以降を参照して下さい。

完全グラフ $K_5$ が平面的グラフでないことの証明

補足：

$2e=\displaystyle\sum_{F_0\in F}e(F_0)\geq\displaystyle\sum_{F_0\in F}3=3f$

ただし，$F$ は面全体の集合，$e(F_0)$ は $F_0$ に隣接する辺の数です。

完全グラフ $K_{3,3}$ が平面的グラフでないことの証明

大筋はさきほどと同じですが，$K_{3,3}$ の場合には $e\leq 3v-6$ ではうまくいきません。二部グラフであることを使ってより強い不等式を導きます。

クラトフスキーの定理

最後に，非常に発展的ですがクラトフスキーの定理を紹介しておきます。与えられたグラフが平面的グラフかどうか判定するために使える偉大な定理です。

• 「マイナーとして」という部分は厳密に説明するのはやや大変です，気になる人は調べてみてください。
• $K_5$ や $K_{3,3}$ は平面的グラフではないということから $\Rightarrow$ は上記の議論でなんとなく納得できるでしょう。
• $\Leftarrow$ がすごい結果です。証明はかなり難しいです。