1. 高校数学の美しい物語
  2. 平面グラフとオイラーの定理の応用

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

更新日時 2021/03/07

完全グラフ K5K_5 および完全二部グラフ K3,3K_{3,3} は平面的グラフでない(平面に交差なしで書けない)。

目次
  • 平面的グラフとは

  • オイラーの定理

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

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

  • クラトフスキーの定理

平面的グラフとは

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

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

平面への埋め込み

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

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

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

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

オイラーの定理

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

オイラーの定理:

連結な平面的グラフを平面に交差なしで埋め込んだとき,頂点の数を vv ,辺の数を ee ,面の数を ff (一番外側の領域も一つの面とみなす)とすると ve+f=2v-e+f=2 が成立する。

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

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

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

方針:オイラーの定理を用いて, 「平面的グラフなら辺の数は多過ぎない」という不等式を導きます。そして,K5K_5 は辺の数が多すぎてその制約を破っていることを示します。

証明

完全グラフK_5

平面的グラフは平面に交差なしで埋め込める。

K5K_5 が平面に交差なしで埋め込めたとする。このとき,以下の2つが成立する。

1. 各辺はちょうど2つの面の境界である

理由:平面に埋め込まれたグラフにおいて,各辺には「両側」があるため,2つ以下の面の境界となる。ある辺が閉路に含まれている時,閉路によって辺の「両側」は分断されるので,2つの異なる面の境界になる。そして,K5K_5 ではすべての辺が閉路に含まれている。

2. 各面は3つ以上の辺に囲まれる

理由:平面に埋め込まれたグラフにおいて,各面の境界は閉路を含む(そもそも閉路が存在しないグラフは例外だが,K5K_5 は閉路を含む)。そして,単純グラフでは閉路の長さは3以上である。

上記の1と2より,2e3f2e\geq 3f が成立する(→補足)。

これにオイラーの定理: f=2v+ef=2-v+e を用いて ff を消去すると,

2e3(2v+e)2e\geq 3(2-v+e)

よって,e3v6e\leq 3v-6 を得る。

しかし,K5K_5v=5,e=10v=5,e=10 であり,上の不等式を満たしていないので,背理法により平面的グラフではない。

補足:

2e=F0Fe(F0)F0F3=3f2e=\displaystyle\sum_{F_0\in F}e(F_0)\geq\displaystyle\sum_{F_0\in F}3=3f

ただし,FF は面全体の集合,e(F0)e(F_0)F0F_0 に隣接する辺の数です。

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

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

証明

完全二部グラフK_3,3

K3,3K_{3,3} が平面に交差なしで埋め込めたとする。このとき,さきほどと同様に考えると,以下の2つが成立する。

1. 各辺はちょうど2つの面の境界である

  1. 各面は4つ以上の辺に囲まれる

(2については,単純二部グラフの閉路の長さが 4以上になることからわかる)

したがって,さきほどと同様に 2e4f2e\geq 4f を得る。

オイラーの定理と合わせて,

e2(2v+e)e\geq 2(2-v+e) ,つまり e2v4e\leq 2v-4

しかし,K3,3K_{3,3}v=6,e=9v=6,e=9 であり上の不等式を満たしていないので平面的グラフではない。

クラトフスキーの定理

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

クラトフスキー(Kuratowski)の定理:

グラフ GG が平面的グラフ     \iffGGK5K_{5} および K3,3K_{3,3} をマイナーとして含まない。

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

K5K_5K3,3K_{3,3} は平面的グラフではありませんが,実はドーナツの表面には交差なしで埋め込めます。

人気記事
  1. 高校数学の美しい物語
  2. 平面グラフとオイラーの定理の応用