平面グラフには次数が5以下の点が必ず存在する

平面グラフの話題の続きです。以前、平面グラフの頂点数、辺数、面数に対して成り立つ次のオイラーの公式について述べました。

 

平面グラフに関するオイラーの公式

平面グラフの頂点数、辺数、面数をそれぞれv,e,f とすると、次が成り立つ。

 \displaystyle v-e+f=2

この定理自体の証明もなかなか面白いです。興味のある方はリンク先をご覧ください。

オイラーの公式v-e+f=2 – 数学と高校教師

 

今回はオイラーの公式を利用して、平面グラフの最低次数に関する定理を証明します。なお次数とは頂点を端にもつ辺の個数のことで、ようするに”頂点からでている辺数”を表します。頂点 xの次数を記号\displaystyle \deg(x) と表します。例えば次の図をご覧ください。

 :20180710114102j:plain

上図の\displaystyle x_1,x_2,x_3 の次数はそれぞれ\displaystyle 6,4,1 です。記号で表すと

 \displaystyle \deg(x_1)=6, \deg(x_2)=4, \deg(x_3)=1

となります。

さて、平面グラフはいくらでも複雑なものが作れるので、どの頂点も次数が10以上とか、どの頂点も次数が100以上とか、いくらでも最低次数が大きいグラフがかけそうな気もするのですが、実は「どんなに複雑に平面グラフを書いても、次数が5以下の頂点がある」ことが知られています。

 

平面グラフの最低次数

平面グラフには次数が5以下の頂点が存在する。

では、上の定理の証明のために、平面グラフの辺数\displaystyle e を上から評価する次の補題を示します。

 

補題

頂点数\displaystyle 3 以上の平面グラフにおいては

 \displaystyle e\leqq 3v-6 …(⭐︎)

が成立する。

(証明)

平面グラフ\displaystyle G の各辺の両側に小石を1個ずつ置いたところを想像してほしい。

 :20180709234630j:plain

面は少なくとも\displaystyle 3 つの辺で囲まれるので、どの面にも3個以上の小石が配置されることになる。すなわち

 \displaystyle 2e \geqq 3f …①

が成り立つ。一方オイラーの公式を3倍すると

 \displaystyle 3v-3e+3f=6 …②

となる。①と②から

 \displaystyle 3v-3e+2e\geqq 6

すなわち

 \displaystyle 3v-6\geqq e

が成り立つ。(証明終)

 

では、目標の証明に移ります。

平面グラフの最低次数(再掲)

平面グラフには次数が5以下の頂点が存在する。

(証明)

一般に、各頂点\displaystyle x の次数\displaystyle \deg(x) の和について

 \displaystyle \sum \deg(x)=2e …③

 が成り立つことに注意しよう(握手補題)。これは上の議論と同様に各辺に対して辺をまたぐように2個ずつ小石を置いたとき、

・小石の個数=頂点の次数の和

であり、また

・小石の個数=辺数の2倍

でもあることからわかる。

では、定理の証明に移ろう。すべての頂点の次数\deg(x) が6以上となるような平面グラフが存在したとすると、③(握手補題)により

 \displaystyle 2e=\sum\deg(x)\geqq  6v

すなわち

 \displaystyle  e\geqq 3v

\displaystyle e の下からの評価が成り立つ。補題で証明した\displaystyle e を上から評価する式(⭐︎)と組み合わせると、

 \displaystyle 3v\leqq e \leqq 3v-6

となり矛盾が生じる。よってすべての頂点の次数が6以上の平面グラフは存在しない。(証明終)

 

論理で存在が証明できるのは数学の強さを感じますね!いつか近いうちこの定理を利用して四色定理関連の話をします。

 

では今回はこの辺で。