グラフ理論について（３）

みなさん、こんにちは。

今回はオイラーの多面体定理について紹介していきたいと思います。

オイラーの多面体定理は高校1年生の教科書で出てくる定理です。
しかし、大学入試ではほとんど出題されることがないため、影が薄い定理であると私は感じています。

ということで、今回はこのオイラーの多面体定理を主役に記事を書いていこうと思います。

【１】オイラーの多面体定理とは？

まずは、オイラーの多面体定理について紹介します。

V、E、F　をそれぞれ凸多面体の頂点、辺、面とするとき、
V-E＋F＝2という式が成り立ちます。

V、E、F　は頂点(vertex)、辺(edge)、面(face)の頭文字からとっています。

では、この式がなぜ成り立つのかについて証明していきたいと思います。

【２】オイラーの多面体定理の証明

※今回は単純グラフについて考えます。
　なぜなら、凸多面体において、ループや多重辺は存在しないからです。

グラフの「ループ」や「多重辺」などの用語については上の記事でまとめているので、そちらを参考にしてみて下さい。

空間を考える前に、まずは、平面について考えてみましょう。

平面のグラフについて、このような定理が成り立ちます。

V、E、F　をそれぞれ平面のグラフの頂点、辺、面とするとき、
V-E＋F＝１という式が成り立ちます。

オイラーの多面体定理の右辺である「＝２」の部分が、「＝１」というように変わっていますが、それ以外は一緒ですね。

①木について

木とは閉路をもたない連結なグラフのことをいいます。下のようなグラフが木とよばれるグラフです。

木には、面が存在しないので、頂点と辺を数えてみましょう。
左のグラフは頂点の数が４、辺の数が３であるので、４－３＝１
真ん中のグラフは頂点の数が７、辺の数が６であるので、７－６＝１
右のグラフは頂点の数６、辺の数が５であるので、６－５＝１
よって、V-E＋F＝１　という式が成り立つことが分かります。

〈証明〉
●（頂点）と　ー（辺）をそれぞれ1個ずつ取り除く。
すると、●（頂点）が1つ余るので、V-E＋F＝１が成り立つ。□

②閉路のある平面上のグラフ

今度は閉路のあるグラフについて考えてみましょう。
閉路があるとき、頂点と辺のほかに面も数えます。

頂点の数が５、辺の数が７、面の数が３であるので、５－７＋３＝１
よって、閉路がある場合も　V-E＋F＝１　が成り立つことが分かります。

〈証明〉
まず、閉路がなくなるように　ー（辺）を取り除く。
すると、面の数が1減り、辺の数も1減る。
閉路がなくなると、木のグラフになるため、あとは①と同様の作業を行う。
よって、V-E＋F＝１が成り立つ。　　　　　　　　　　　　　　　　　□

③空間のグラフ

空間のグラフでは、V-E＋F＝２　が成り立ちます。
では、この式がなぜ成り立つのか考えてみましょう。

まずは、上の図で示されている立方体(正六面体)について考えてみます。
空間図形で考えるのは大変であるので、平面で考えてみます。
青で示された面を取り除き、広げて上から下に押しつぶします。
すると、右のようなグラフができます。

頂点の数は８、辺の数は１２、面の数は５より、８ー１２＋５＝１となる。
また、取り除いた１つの面をたすと、V-E＋F＝２　が成り立ちます。

正八面体のときも考えてみましょう。
立方体（正六面体）のときと同様に考えます。
赤で示した面を取り除き、広げて上から押しつぶします。
すると、右のようなグラフができます。

頂点の数は６、辺の数は１２、面の数は７より、６－１２＋７＝１となる。
また、取り除いた１つの面をたすと、V-E＋F＝２　が成り立ちます。

〈証明〉
まず、1つの面を選び、取り除く。
次にその面を広げて押しつぶし、平面上のグラフを作る。
②より、平面上のグラフでは　V-E＋F＝１　が成り立つ。
はじめに、１つの面を取り除いているので、1つの面をたすと、
V-E＋F＝２　が成り立つ。

【３】正多面体はなぜ5種類しかないのか

①正多面体の定義について

まず、正多面体の定義について確認しましょう。

凸多面体で、
（ⅰ）すべての面が合同な正多角形
（ⅱ）各頂点に集まる辺の数が一定
となるものを正多面体（プラトンの多面体）という。

上の５つ図形が正多面体になります。
左から、正四面体、正六面体、正八面体、正十二面体、正二十面体です。
他にも色々ありそうですが、この5種類しかありません。

②正多面体に関する定理とその証明

正多面体は正四面体、正六面体、正八面体、正十二面体、正二十面体
の5種類しか存在しない。

では、上の定理を証明していきましょう。

〈証明〉
多面体の頂点の数を V，辺の数を E，面の数を F とする。
立体の面が正 n角形，1つの頂点に集まる辺が k 本であるとする。( n , k ≧ 3 )

そのとき、それぞれの頂点にk本の辺が集まり、一つの辺は二つの頂点に集まるから　kV=2E　･･･①　
それぞれの面には辺がn本あり、一つの辺は二つの面に含まれるから　
Fn=2E　･･･②　が成り立つ。
また、オイラーの多面体定理より、V－E＋F＝2　･･･③　

①、②、③より、2E/ｋ−Ｅ+2Ｅ/ｎ= 2 　
　　　　　　　　　　　 2/ｋ+2/ｎ=2/Ｅ+1>1
　　　　　　　　　　　　　  　(k−2)(n−2) < 4

これを満たす組  (n , k) は (n , k )=( 3 , 3 ),( 3 , 4 ),( 3 , 5 ),( 4 , 3 ),( 5 , 3 )

したがって、正多面体は5種類しか存在しない。
そして、それらの組は正四面体、正六面体、正八面体、正十二面体、
正二十面体と対応している。　　　　　　　　　　　　　　　　　　　□

【４】最後に

今回は、オイラーの多面体定理と正多面体が５種類しか存在しないことについて紹介しました。

次回は、パーティー問題について紹介していきたいと思います。

最後まで読んでいただき、ありがとうございました。