グラフの「かたち」は何を決めるのか ― 平面性から四色定理へ

平面グラフは辺数が $3V - 6$ 以下に抑えられ，一般のグラフで困難な問題も効率的に解けます．オイラーの公式 $V - E + F = 2$，Kuratowski の定理，そして四色定理の哲学的意味を直感的に解説します．

2026年2月27日

これまでの記事では，グラフを「頂点と辺の集合」として扱い，その組合せ的構造を調べてきました．しかし，グラフには幾何学的な側面もあります．グラフを平面上に辺が交差しないように描けるかどうか ― この平面性という性質が，驚くほど多くのことを決定します．

1 平面グラフとは

定義 1 (平面グラフ).

グラフ

G

を平面上に描いたとき，辺同士が（端点以外で）交差しないような描画が存在するとき，

G

を平面的（planar）であるといいます．実際にそのように描画されたものを平面グラフと呼びます．

例 2.

K_{4}

（完全グラフ，4頂点）は平面的です．正四面体の1つの面を外側に開くように描くと，辺の交差なしに描けます．

しかし，頂点が5個（ $K_{5}$ ）や，辺の配置が特殊（ $K_{3, 3}$ ）になると，もはや交差なしには描けません．

2 オイラーの公式 ― トポロジカル不変量

平面グラフの最も基本的な性質がオイラーの公式です．

定理 3 (オイラーの公式).

連結平面グラフにおいて，頂点数

V

，辺数

E

，面数

F

は以下を満たします：

V - E + F = 2

例 4.

K_{4}

を平面に描くと，

V = 4

E = 6

F = 4

（三角形3つ + 外側の面1つ）で

4 - 6 + 4 = 2

です．

注意 5 (オイラーの公式の驚き).

この公式が驚くべきなのは，

V - E + F

の値がグラフの描き方に依存しないということです．同じグラフをどんな風に平面に描いても，

V - E + F = 2

が成り立ちます．

これは位相幾何学（トポロジー）の言葉で言えば，

V - E + F

がオイラー標数というトポロジカル不変量であるということです．平面のオイラー標数が2であることの反映です．

トーラス（ドーナツの表面）上のグラフでは

V - E + F = 0

となります．面の概念はグラフを描く「面」に依存するのです．

3 平面グラフの辺数の上界 ― 疎性の保証

オイラーの公式から，平面グラフの辺数に強い制約が得られます．

定理 6 (平面グラフの辺数上界).

V \geq 3

の単純連結平面グラフにおいて

E \leq 3 V - 6

注意 7 (導出の直感).

平面グラフの各面は少なくとも3本の辺に囲まれています（ループや多重辺を除く）．各辺はちょうど2つの面に接するので

3 F \leq 2 E

，すなわち

F \leq 2 E /3

です．これをオイラーの公式

V - E + F = 2

に代入すると

V - E + \frac{2 E}{3} \geq 2 ⟹ E \leq 3 V - 6

が得られます．

例 8 (

K_{5}

が平面的でないことの証明).

K_{5}

は

V = 5

E = 10

です．

3 V - 6 = 9 < 10 = E

なので，

K_{5}

は平面的ではありません．

定理 9 (二部平面グラフの辺数上界).

二部グラフかつ平面的なグラフでは，

E \leq 2 V - 4

が成り立ちます（三角形の面がないため

4 F \leq 2 E

を使う）．

例 10 (

K_{3, 3}

が平面的でないことの証明).

K_{3, 3}

は二部グラフで

V = 6

E = 9

です．

2 V - 4 = 8 < 9 = E

なので，

K_{3, 3}

は平面的ではありません．

4 Kuratowski の定理 ― 平面性の完全な特徴づけ

$K_{5}$ と $K_{3, 3}$ が平面的でないことは辺数の議論で示せました．Kuratowski は，この2つが平面性の唯一の障害であることを証明しました．

定理 11 (Kuratowski の定理).

グラフ

G

が平面的でないための必要十分条件は，

G

が

K_{5}

または

K_{3, 3}

の細分を部分グラフとして含むことです．

定義 12 (細分).

グラフ

H

の辺を，いくつかの辺の列（パス）に置き換えて得られるグラフを

H

の細分（subdivision）と呼びます．

注意 13.

直感的に言えば，グラフが平面的でない理由は2つしかありません：

5つの「もの」がすべて互いに結ばれている（ $K_{5}$ 型）
3つの「もの」と3つの「もの」がすべて結ばれている（ $K_{3, 3}$ 型，別名「3軒の家と3つの公共施設問題」）

どんな非平面的グラフも，突き詰めるとこの2つのパターンのどちらかに帰着するのです．

5 平面性が計算を楽にする

$E \leq 3 V - 6$ という上界は， $E = O (V)$ を意味します．一般のグラフでは $E = O (V^{2})$ になり得るので，平面グラフは本質的に疎（sparse）です．

注意 14 (計算量への影響).

多くのグラフアルゴリズムの計算量は

O (V + E)

や

O (E lo g V)

の形をしています．平面グラフでは

E = O (V)

なので：

BFS, DFS: $O (V + E) = O (V)$
Dijkstra（ヒープ使用）: $O (E lo g V) = O (V lo g V)$
一般のグラフで $O (V^{2})$ かかるアルゴリズムが $O (V)$ になることがある

さらに，平面グラフでは一般のグラフで NP 完全な問題が効率的に解けることがあります．

定理 15 (平面グラフの分離定理).

n

頂点の平面グラフは，

O (n)

個の頂点を除去することで，サイズがそれぞれ

2 n /3

以下の2つの部分に分割できます．

この分離定理は分割統治法を可能にし，多くの問題に準指数時間アルゴリズムや PTAS（多項式時間近似スキーム）を与えます．

6 四色定理 ― 150年の挑戦

平面グラフの彩色に関する最も有名な結果が四色定理です．

定理 16 (四色定理 (Appel-Haken, 1976)).

任意の平面グラフは4色で彩色可能です：

χ (G) \leq 4

．

注意 17 (四色定理の哲学的意味).

四色定理は1852年に予想されてから証明まで124年を要しました．しかもその証明はコンピュータによる場合分け（1000以上のケース）に依存しており，「人間が通読して検証できる証明」がいまだに存在しません．

これは数学の哲学に深い問いを投げかけました：

コンピュータによる証明は「証明」として認めてよいのか？
人間が理解できない証明に数学的意味はあるのか？

数学界は最終的にこの証明を受け入れましたが，「エレガントな証明」を求める試みは今も続いています．

四色で十分なことは非自明ですが，5色で十分なことは比較的簡単に示せます．

定理 18 (五色定理).

任意の平面グラフは5色で彩色可能です：

χ (G) \leq 5

．

注意 19 (五色定理の直感).

E \leq 3 V - 6

から，平面グラフには次数5以下の頂点が必ず存在します（平均次数が

2 E / V < 6

なので）．この頂点を取り除いて帰納法を適用し，戻すときに高々5つの隣接頂点が使っている色を避ければよい ― これが五色定理の基本的な流れです．

4色に下げるには，この議論だけでは足りず，Kempe 鎖と呼ばれるテクニックで色の付け替えが必要になります．Kempe 自身は1879年にこの方法で四色定理を「証明」しましたが，11年後に Heawood が誤りを発見しました（しかし Kempe の議論は五色定理の証明としては正しいことも示しました）．

7 まとめ

平面グラフ：辺の交差なしに平面に描けるグラフ
オイラーの公式 $V - E + F = 2$ は，平面グラフの基本的なトポロジカル不変量
$E \leq 3 V - 6$ により平面グラフは疎であり，アルゴリズムが高速に動く
Kuratowski の定理： $K_{5}$ と $K_{3, 3}$ の細分が唯一の非平面性の障害
四色定理：任意の平面グラフは4色で塗れる（証明にコンピュータを使用）

8回にわたるグラフ理論「教科書の行間」シリーズはこれで完結です．グラフという抽象化が，ケーニヒスベルクの橋から計算量理論，位相幾何学まで，どれほど広い世界に通じているかを感じていただけたなら幸いです．

グラフ理論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

グラフの「かたち」は何を決めるのか ― 平面性から四色定理へ

1 平面グラフとは

2 オイラーの公式 ― トポロジカル不変量

3 平面グラフの辺数の上界 ― 疎性の保証

4 Kuratowski の定理 ― 平面性の完全な特徴づけ

5 平面性が計算を楽にする

6 四色定理 ― 150年の挑戦

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ