5-1 平面グラフ
交差は描き方の問題か、構造の問題か
$K_4$ を四角形と二本の対角線として描くと、対角線が交差します。しかし一頂点を三角形の内側へ移せば、辺を交差させずに描けます。交差する図を一つ見つけても、グラフが平面に描けない証明にはなりません。
一方 $K_5$ は、どのように頂点を置き、辺を曲げても交差なしには描けません。この違いを調べるには、「グラフ」と「具体的な平面上の描画」を区別する必要があります。
planar graphとplane graph
グラフ $G$ が平面的グラフ|planar graphであるとは、頂点を平面上の相異なる点、辺をその端点を結ぶ有限simple polygonal arcとして、異なる辺の内部が交わらないように描けることをいう。
交差なしの具体的な描画が一つ固定されたグラフを平面グラフ|plane graphという。
plane graphの描画を平面から除いた残りの連結成分を面 (グラフ理論)|面という。外側へ無限に広がる成分も一つの面として数え、外面という。
本書では平面分離の依存を有限polygonal版で閉じるため、plane drawingをpolygonal arcによる描画として定義します。有限graphについて、一般の単純arcによる埋め込み、polygonal埋め込み、直線辺による埋め込みが同じplanarity概念を与えることは、Fáryの定理を含む別の構造問題です。本書の全構成とKuratowski定理は上のpolygonal定義だけで完結します。
同じplanar graphでも描き方により面の境界は変わることがあります。しかし面の個数はEuler公式によって頂点数と辺数から決まり、描き方に依存しません。
面の境界では辺を重複して数える
面の周囲を歩いたときに通る辺の本数を、その面の次数と呼びます。bridgeは同じ面の境界を両側から支えるため、同じ面の境界に二度現れます。
例えば木を平面に描くと面は外面一つだけです。辺が $n-1$ 本なら外面の境界walkでは各辺を往復し、面次数は $2(n-1)$ です。
plane graph $G$ の面全体を $F(G)$ とすると、境界での重複を込めて
$$
\sum_{f\in F(G)}\deg(f)=2|E(G)|.
$$
各辺の細い近傍には二つの側があります。辺が二つの異なる面を隔てる場合は各面の境界に一度ずつ現れます。bridgeのように両側が同じ面に接する場合は、その面の境界に二度現れます。いずれの場合も一辺は面次数の総和へちょうど2を寄与します。全辺について足せば結論を得ます。□
平面上の閉曲線について使う事実
Euler公式の証明では、次の初等的な平面の事実を使います。
plane graphの一つの面の境界上にある二点を、その面の内部を通る単純arcで結ぶと、その面は二つに分かれる。従って頂点数を変えず辺を一本加えると、面数はちょうど1増える。
追加したarcの両端を結ぶ面境界上のwalkを一つ選ぶと、arcと境界walkから不要な反復部分を除いて単純閉曲線を得られます。単純閉曲線は平面を内側と外側の二領域に分け、その曲線を横切らずには一方から他方へ移れません。追加arcの両側にあった面内の小領域は異なる連結成分に分かれます。
元の面のどの点もarcのいずれか一方の側から到達でき、他の面は変更されません。従って元の一面が二面になり、面数は1増えます。ここで使った有限polygonal曲線の内外二成分とcrossing corollaryは、折れ線に対するJordan曲線定理から従います。□
本書で使うのは、cycleまたは有限本のpolygonal arcから作る単純閉曲線に対する定理だけです。一般の連続Jordan curveは必要としません。
Euler公式
有限連結plane graph $G$ の頂点数を $v$、辺数を $e$、面数を $f$ とすると
$$
v-e+f=2.
$$
$G$ は連結なので全域木 $T$ をもちます。$T$ は $v$ 頂点 $v-1$ 辺です。
まず平面に描かれた木 $T$ の面は一つです。頂点一つなら明らかです。頂点数2以上なら葉とその接続辺を削ると小さい木になり、帰納法で面は一つです。葉と一本の突き出した辺を戻しても閉曲線は作らず、面を二つに分けないため面数は一つのままです。従って木では
$$
v-(v-1)+1=2.
$$
元のplane graph $G$ のうち $T$ にない辺を、元の描画に従って一本ずつ戻します。戻す辺の内部は既に戻したグラフと交わらず、一つの面の内部にあります。面を横切るarcの補題により、一本戻すごとに辺数と面数がともに1増えます。従って $v-e+f$ の値は変わりません。
すべての辺を戻すと $G$ になり、その値は木のときと同じ2です。□
例：立方体グラフ
立方体の頂点と辺をgraphとして平面に描くと
$$
v=8,\qquad e=12.
$$
Euler公式から
$$
f=2-v+e=2-8+12=6.
$$
立方体の六つの正方形面と一致します。平面描画ではその一つが外面になります。
非連結の場合
$c$ 個の連結成分をもつ有限plane graphについて
$$
v-e+f=1+c.
$$
異なる連結成分を結ぶように、既存の辺と交差しない辺を $c-1$ 本加えて連結にできます。異なる成分を結ぶ辺はcycleを作らず、一つの面の内部にbridgeとして置かれるので面数は変わりません。
得られた連結plane graphは頂点数 $v$、辺数 $e+c-1$、面数 $f$ です。連結版のEuler公式から
$$
v-(e+c-1)+f=2.
$$
整理すると $v-e+f=1+c$。□
simple planar graphの辺数上界
Euler公式だけでは $K_5$ の非平面性はまだ見えません。各面が少なくとも三辺に囲まれることを合わせます。
$v\ge3$ のsimple planar graph $G$ に対して
$$
e\le3v-6.
$$
辺を追加して各成分を結んでもsimpleかつplanarに保てるため、$G$ を連結としてよいです。固定したplane描画を考えます。
simple graphにはloopも平行辺もないので、各面の境界次数は少なくとも3です。bridgeがある場合も、その辺は境界で往復しますが、$v\ge3$ の連結simple graphでは面境界全体の長さが2になることはありません。従って面次数の和から
$$
3f\le\sum_f\deg(f)=2e.
$$
Euler公式 $v-e+f=2$ より $f=2-v+e$。代入して
$$
3(2-v+e)\le2e,
$$
従って
$$
e\le3v-6.
$$
□
この証明の「各面次数は3以上」は、木 $P_3$ の外面次数4でも成立します。ただし $K_2$ では外面次数2となるため $v\ge3$ が必要です。
$K_5$ は非平面
$K_5$ は
$$
v=5,\qquad e=\binom52=10
$$
です。もしplanarなら辺数評価により
$$
10=e\le3\cdot5-6=9
$$
でなければならず矛盾します。従って $K_5$ は非平面です。
bipartite planar graphのより強い評価
二部グラフには奇cycleがなく、特に三角形がありません。そのため面は少なくとも四辺に囲まれます。
$v\ge3$ のsimple bipartite planar graph $G$ に対して
$$
e\le2v-4.
$$
前と同様、連結なplane描画を考えてよいです。二部グラフのclosed walkの長さは偶数で、simple graphに長さ2のcycleはありません。従って辺をもつ各面の境界次数は少なくとも4です。木の場合は $e=v-1\le2v-4$ が $v\ge3$ で直接成り立つので、cycleをもつ場合を考えれば全ての面について
$$
4f\le2e.
$$
Euler公式から
$$
4(2-v+e)\le2e,
$$
ゆえに
$$
e\le2v-4.
$$
□
$K_{3,3}$ は非平面
$K_{3,3}$ は二部グラフで
$$
v=6,\qquad e=3\cdot3=9.
$$
もしplanarなら
$$
9=e\le2\cdot6-4=8
$$
となり矛盾します。従って $K_{3,3}$ は非平面です。
$K_5$ と $K_{3,3}$ は平面性を妨げる二つの基本形です。辺数評価はこの二つを見抜きますが、すべての非平面グラフを見抜くわけではありません。辺を途中で分割して頂点を増やすと上界を満たすようになっても、非平面性は変わらないからです。これがKuratowskiの定理へつながります。
三角形分割と極大planar graph
$v\ge3$ の連結simple plane graphで、すべての面の境界次数が3なら
$$
e=3v-6,\qquad f=2v-4.
$$
面次数の和から $3f=2e$。Euler公式 $v-e+f=2$ へ $f=2e/3$ を代入すると
$$
v-e+\frac{2e}{3}=2,
$$
従って $e=3v-6$。さらに
$$
f=\frac{2e}{3}=2v-4.
$$
□
辺をこれ以上交差なしに加えられない極大simple planar graphでは、適切な条件下で全ての面が三角形になります。従って上界 $3v-6$ は単なる粗い評価ではなく、実際に達成されます。
演習
ある連結plane graphが12頂点18辺をもつ。面数を求めよ。
Euler公式から
$$
12-18+f=2,
$$
従って $f=8$ です。外面も一つとして数えています。□
連結simple plane graphで、各頂点の次数が5、各面の次数が3であるとする。頂点数、辺数、面数を求めよ。
握手補題と面次数の和から
$$
5v=2e,\qquad3f=2e.
$$
従って $v=2e/5,f=2e/3$。Euler公式へ代入すると
$$
\frac{2e}{5}-e+\frac{2e}{3}=2.
$$
左辺の係数は $(6-15+10)/15=1/15$ なので $e=30$。従って
$$
v=12,\qquad f=20.
$$
正二十面体のgraphに対応します。□
すべての $n\ge1$ に対して $K_{2,n}$ がplanarであることを、交差しない描き方を言葉で構成して示せ。辺数評価と矛盾しないことも確認せよ。
二頂点 $u,v$ を置き、その間を結ぶ、内部では互いに交わらない $n$ 本のarcを平行に描きます。第 $i$ のarcの内部に頂点 $w_i$ を一つ置き、そのarcを $uw_i$ と $w_iv$ の二辺に分けます。異なるarcは端点 $u,v$ 以外で交わらないので、これは $K_{2,n}$ のplane描画です。
$v=n+2,e=2n$ なので、二部planar上界は
$$
2n\le2(n+2)-4=2n
$$
と等号で成立します。□
$K_{3,3}$ の各辺を一度ずつ分割して新頂点を9個加えたグラフ $H$ を考える。$H$ が $e\le3v-6$ を満たすが非平面であることを示せ。
元の $K_{3,3}$ は6頂点9辺です。各辺を分割すると、一辺が二辺になるため
$$
v(H)=6+9=15,\qquad e(H)=18.
$$
確かに
$$
18\le3\cdot15-6=39.
$$
もし $H$ がplanarなら、各次数2の新頂点の近くで二本の辺を滑らかにつなぎ、その頂点を消すことで $K_{3,3}$ のplane描画が得られます。しかし $K_{3,3}$ は非平面なので矛盾です。従って $H$ は非平面です。辺数上界は必要条件であって十分条件ではありません。□
$v\ge3$ の連結simple planar graphが三角形を含まないなら
$$
e\le2v-4
$$
であることを示せ。二部性は仮定しない。
三角形を含まないため、各面境界の長さは3にはなれません。simple graphなので長さ1,2もなく、cycleを含む場合は各面次数が少なくとも4です。木なら $e=v-1\le2v-4$。
従ってcycleを含む場合は
$$
4f\le2e.
$$
Euler公式と同じ計算から $e\le2v-4$ を得ます。二部グラフでなくても、三角形がないことだけで証明に必要な面次数下界が得られます。□
$v\ge3$ のsimple planar graphには次数5以下の頂点が存在することを示せ。
すべての頂点の次数が6以上だと仮定すると、握手補題から
$$
2e=\sum_v\deg(v)\ge6v,
$$
従って $e\ge3v$ です。しかしplanar辺数上界は
$$
e\le3v-6<3v
$$
なので矛盾します。ゆえに少なくとも一頂点は次数5以下です。この事実が五色定理の帰納法の入口になります。□
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
