書記が数学やるだけ#629 オイラーの多面体定理，グラフの平面性

グラフの平面性を考える上で，オイラーの多面体定理が重要になってくる。

問題

これらは彩色問題を解くのにも用いられる。

説明

オイラーの多面体定理について，球面に位相同型な多面体については，頂点，辺，面の数について「(頂点の数) + (面の数) - (辺の数) = 2」が成り立つ。正多面体が5つしかないことは，プラトンが『ティマイオス』で言及したように古代ギリシアで既に認識されていたようだが，その証明はオイラーの時代まで待つこととなった。なお，一般の多面体については「(頂点の数) + (面の数) - (辺の数) = オイラー標数」と拡張できる。

さて，グラフ理論において平面的グラフとは「平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフ」を指す。平面的グラフについては色々と制約が多いことから，以下のような不等式が成り立つ。

平面的でないものの代表例として完全グラフK5と完全二部グラフK3,3が挙げられるが，実はこれらを含まないことが平面的であることの必要十分条件であることがわかっている。

解答

オイラーの多面体定理を証明するには帰納法を用いて，辺を1つずつ除去した場合を考える。

オイラーの多面体定理を用いることで，平面的グラフの条件を絞ることができる。

「全ての平面的グラフは位数5以下の点がある」ことは彩色問題の証明の中核である。

ピーターセングラフは非平面的グラフの代表例である。

必要な平面的グラフの最小数を厚さという。複雑な電気回路を構築するには，基盤を厚さの分だけ用意すれば良い。

本記事のもくじはこちら：