平面グラフ ― 平面に描けるグラフの世界
オイラーの多面体公式$V-E+F=2$，$E \leq 3V-6$，$K_5$と$K_{3,3}$の非平面性，Kuratowskiの定理，双対グラフを証明する．
1 平面グラフの定義
定義 1 (平面グラフ).
グラフ が平面的（planar）であるとは， を辺の交差なしに平面 に描くことができることをいう．そのような描画（埋め込み）を の平面描画（plane drawing）といい，平面描画が与えられたグラフを平面グラフ（plane graph）という．
例 2.
（4頂点の完全グラフ）は平面的である．正四面体の1つの面を外側に展開すれば，辺の交差なしに描ける．一方， が平面的でないことは後で証明する．
2 面とオイラーの公式
定義 3 (面).
平面グラフ の平面描画において，辺と頂点を取り除いた後に残る平面の各連結領域を面（face）という．無限に広がる領域を外面（outer face）と呼ぶ．面の数を で表す．
例 4.
の平面描画では，三角形の面が3つと外面1つの計 である．， なので ．
定理 5 (オイラーの公式).
を頂点数 ，辺数 ，面数 の連結平面グラフとする．このとき
証明.
辺の数 に関する帰納法で示す．基底： ならば は連結なので頂点1つからなり，，（外面のみ）．よって ．帰納段階： とし， 本以下の辺を持つ連結平面グラフに対して公式が成り立つと仮定する．辺 を1本取る．場合1： が橋である（ を除くと非連結になる）場合． を除くと2つの連結成分 ， が得られ， に接する2つの面は1つに統合される．帰納法の仮定より （）．，，（外面の統合を考慮）なので ．場合2： が橋でない場合． は閉路に含まれるので， を除いても は連結のまま． の両側の2つの面が1つに統合されるので ，，．帰納法の仮定より ，すなわち ． □
注意 6.
オイラーの公式は元々多面体に対して発見された（1752年）．凸多面体の頂点・辺・面は平面グラフの頂点・辺・面に対応するので，多面体公式 はグラフのオイラーの公式の特殊な場合である．
3 辺数の上界
定理 7 ().
の単純連結平面グラフにおいて ．
証明.
各面は少なくとも3本の辺で囲まれる（単純グラフなのでループや多重辺がない）．各辺はちょうど2つの面に接するので，面の辺数の総和を とすると かつ ．よって ，すなわち ．オイラーの公式 を代入して
整理すると ． □
定理 8 ( 型の上界).
の単純連結平面グラフが三角形（長さ3の閉路）を持たないならば ．
証明.
三角形がないので各面は少なくとも4本の辺で囲まれる． と より ．オイラーの公式を用いて ，すなわち ． □
4 との非平面性
定理 9.
は平面的でない．
証明.
は ， である．平面的であれば が成り立つはずだが， なので矛盾する． □
：
定理 10.
は平面的でない．
証明.
は ， である． は二部グラフなので奇数長の閉路を持たず，特に三角形がない．よって平面的であれば が必要だが， なので矛盾する． □
：
5 Kuratowskiの定理
定義 11 (細分).
グラフ の辺に頂点を挿入して得られるグラフを の細分（subdivision）という．すなわち，辺 を新しい頂点 と2辺 ， で置き換える操作を有限回行って得られるグラフである．
定理 12 (Kuratowskiの定理（1930年）).
グラフ が平面的であるための必要十分条件は， が の細分も の細分も部分グラフとして含まないことである．
注意 13.
必要性は明らかである：平面グラフの部分グラフは平面的であり，細分も平面性を保存するが， と は平面的でないからである．十分性の証明は長大であり，ここでは割愛する．
6 双対グラフ
定義 14 (双対グラフ).
連結平面グラフ に対して，双対グラフ を次のように定める：
の頂点は の各面に対応する．
の各辺 に対して， が隣接する2つの面に対応する の頂点を結ぶ辺 を置く．
定理 15.
連結平面グラフ の双対 に対して （自然な同型）が成り立つ．
注意 16.
双対グラフにおいて， のカットと の閉路が対応する．この双対性はネットワーク理論やマトロイド理論で重要な役割を果たす．