📂グラフ理論

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

概要

オイラーの多面体定理は、グラフ理論では単にオイラーの公式とも呼ばれる。幾何学的には、空間図形の点、線、面が#点-#線+#面=2の関係に従うという意味を持つ。例えば、立方体を考えると、$8$個の点と$12$個の線、$6$個の面を持ち、$8-12+6=2$が成り立つ。

定理 ¹

リンク 平面グラフ $G$について、$n:=|V(G)|$、$m:=|E(G)|$、$f$を面の数とした場合 $$ n-m+f=2 $$

---

• 平面グラフが描かれることで、平面上で区別される領域をフェースと呼ぶ。

証明

戦略: 様々なアプローチがあるが、このポストでは基本的なグラフ理論を用いた証明を紹介するつもりだ。場合分けして数学的帰納法を適用すれば、難しくなく証明できる。

---

ケース1. $n=1$

$G$が連結であるため、$m=1$、無限のフェース以外にフェースはないため、$f=1$が成り立つ。したがって、$1-0+1=2$が満たされる。

---

ケース2. $n>1$であり、$G$が木グラフの場合

$G$が木であるため、$m=n-1$が成り立ち、サイクルを含んでいないため、$f=1$が成り立つ。したがって、$n-(n-1)+1=2$が満たされる。

---

ケース3. $n>1$であり、$G$が木グラフでない場合

$G$は少なくとも1つのサイクルを含んでいるが、そのサイクルにあるエッジを$e$としよう。その$e$を除去した新しいグラフ$G-e$について $$ |V(G-e)|=n \\ |E(G-e)|=m-1 $$ その間に、サイクルを囲んでいた$e$を除去することにより、$e$を境にしていた2つのフェースが1つに合体する。したがって、$G-e$のフェースの数は$f-1$となり、$n-(m-1)+(f-1)=n-m-f=2$が成り立つ。

■

一方で、オイラーの多面体定理は、$k$個のコンポーネントに対して次のように一般化される。上記の定理は特に連結グラフ、つまり$k=1$の場合の特殊なケースである。

一般化

平面グラフ$G$について、$n:=|V(G)|$、$m:=|E(G)|$、$f$を面の数、$k$をコンポーネントの数とすると、以下が成り立つ。 $$ n-m+f=k+1 $$ これは、グラフの連結性に関するオイラーの多面体定理の一般化である。

併せて見る

グラフ理論におけるオイラーの指標

元々、オイラーの指標はグラフ理論で最も有名であり、オイラーの多面体定理またはオイラーの公式は、連結平面グラフについて$\chi = 2$が成り立つというグラフ理論の定理である。

幾何学におけるオイラーの指標

ガウス-ボンネの定理の方程式を満たす整数として定義される。

代数トポロジーにおけるオイラーの指標

各次元のベッティ数の交代和として定義される。