5-5 Euler公式と非平面性の判定

1　グラフと描画を区別する

グラフが平面的であるとは、辺を互いに交差しない弧として平面へ描けることをいう。一つの描画を固定したものを平面グラフという。交差する描画が一つあっても、別の描画で交差が消えることがある。例えば $K_4$ は四角形と二本の対角線として描くと交差するが、一頂点を三角形の内部へ置けば平面的である。
本章のEuler計算は、辺を有限本の線分で描き、辺内部同士や辺内部と頂点が交わらない有限単純平面グラフを対象とする。頂点数を $V$、辺数を $E$、補集合の連結成分である面の数を $F$ とし、非有界な外面も数える。グラフの連結成分数は $c$ と書く。

2　Euler公式と橋

定理。 有限連結単純平面グラフでは
$$V-E+F=2\tag{1}$$
証明。 閉路上の辺を一つ消すとグラフは連結のままである。閉路は単純閉折れ線であり、その辺の両側は異なる面に属する。辺を消すとこの二面が合流するので $E,F$ が各1減る。閉路がなくなるまで続けると木になり、その補集合は一つの面である。木では $E=V-1,F=1$ だから式 (1) が成立する。単純閉折れ線の二側が異なる根拠と木の補集合の迂回は、折れ線に対するJordan曲線定理による。□
連結でない場合は $V-E+F=1+c$ となる。異なる二成分を既存の辺に交わらない弧で結ぶと、辺だけが1増えて面数は変わらない。この操作を $c-1$ 回行えば連結になるから、式 (1) から一般式が出る。孤立頂点も一成分として数える。
橋は消すと連結成分数が増える辺である。橋を渡った面境界は、同じ辺の両側をたどることがある。面境界で辺が現れた回数を、向きを区別した境界歩道の長さとして数える。連結平面グラフでは各辺の両側の出現を足して
$$\sum_{f}\deg(f)=2E\tag{2}$$
橋を一度しか数えないと式 (2) を誤る。例えば三頂点の道では $V=3,E=2,F=1$ で、唯一の面の境界歩道の長さは4である。

3　辺数評価と非平面性

連結な単純平面グラフで $V\ge3$ のとき、各面の境界歩道の長さは少なくとも3である。橋は同じ辺を往復するが、三頂点以上の連結単純グラフでは一面全体の境界歩道が長さ2で終わることはない。従って式 (2) から $3F\le2E$。式 (1) と合わせて
$$E\le3V-6\tag{3}$$
$K_5$ なら $V=5,E=10$ だが右辺は9なので、どの描画も平面埋め込みにはならない。
二部グラフでは三角形の面境界がない。連結な単純二部平面グラフで $V\ge3$ なら各面の境界歩道の長さは少なくとも4であり、$4F\le2E$。よって
$$E\le2V-4\tag{4}$$
$K_{3,3}$ は $V=6,E=9$ で右辺は8だから非平面である。この評価は二部性を使う。$K_5$ に式 (4) を適用してはならない。
これらは非平面性の十分な証拠であるが、式 (3)・(4) を満たせば平面的になるという逆向きの判定ではない。辺の分割は $V,E$ を同数ずつ増やしてEuler値を変えず、非平面性を保つこともある。Kuratowski定理の「非平面なら $K_5$ または $K_{3,3}$ の分割を含む」という向きの証明は、「平面性判定の構造」で行う。

4　平面双対を作る

連結な平面グラフの各面に双対頂点を一つ置き、元の各辺を横切る双対辺を、その両側の面の双対頂点の間に引く。この平面双対では、元の面数が双対の頂点数、元の辺数が双対の辺数になる。元の橋の両側は同じ面なので、対応する双対辺はループになる。双対に平行辺が生じることもあるため、単純グラフに限定して双対を考えてはならない。
例えば一つの三角形の平面描画には内面と外面の二つがあり、双対は二頂点の間に平行な三辺をもつ。元の三角形は $(V,E,F)=(3,3,2)$、双対は $(2,3,3)$ で、いずれもEuler値は2である。

5　交互端点の道は同じ側で交差する

有限折れ線に対するJordan曲線定理には、次の直接の帰結がある。単純閉折れ線 $C$ の内側の点と外側の点を結ぶ連続道は $C$ と交わる。もし交わらなければ道の像は $\mathbb R^2\setminus C$ の連結部分集合なのに、その二成分の点をともに含むことになる。
交互端点定理。 $C$ 上の相異なる四点 $a,c,b,d$ がこの巡回順に並ぶとする。$a$ と $b$ を結ぶ単純折れ線弧 $P$、$c$ と $d$ を結ぶ単純折れ線弧 $Q$ があり、両弧の内部は $C$ と交わらず、かつ $C$ の内側または外側の同じ成分に入る。このとき $P\cap Q\ne\varnothing$ である。
証明。 $C$ の $a$ から $b$ への二つの境界弧のうち $c$ を通る方を $A_1$、$d$ を通る方を $A_2$ とする。$J=P\cup A_1$ は単純閉折れ線である。$P,Q$ の内部が入る $C$ の成分を $U$、他方を $U'$ とする。$J$ は $U'$ と交わらない。折れ線Jordan曲線定理の交差偶奇 $\varepsilon_J$ は連結な $U'$ 上で一定であり、その値を $k$ と書く。
$c$ の小さい近傍では $J$ は $A_1\subset C$ と一致する。境界辺を横切ると交差偶奇が反転するから、$Q$ 上で $c$ に十分近い内部点 $c'$ は $\varepsilon_J(c')=1-k$ を満たす。$c$ が頂点でも、境界頂点の局所扇形内では同じ値になる。一方、$d\notin J$ なので $d$ の十分小さい近傍では $\varepsilon_J$ は両側とも $k$ である。$Q$ 上で $d$ に近い内部点 $d'$ では $\varepsilon_J(d')=k$。もし $Q$ が $J$ を避ければ、連結な $Q$ 上で局所定数な $\varepsilon_J$ は一定になり矛盾する。従って $Q$ は $J$ と交わる。$Q$ の内部は $C$ と交わらず、端点 $c,d$ も $J$ にないから、交点は $A_1$ でなく $P$ 上にある。□
この定理により、平面グラフの一つの閉路 $C$ に四つのattachmentが交互に並ぶ二本の道は、共通頂点や辺の交差なしに同じ面側へ置けない。二本の道を内側と外側に分ければ、定理の「同じ側」という仮定は満たされない。

6　演習と解答

演習1。 立方体のグラフの $V,E,F$ を求めよ。
解答。 $V=8,E=12$。式 (1) から $F=2-8+12=6$。六つの正方形面を数える結果と一致する。
演習2。 四頂点の道と三頂点の道を離して描いたときの $V,E,F,c$ とEuler値を求めよ。
解答。 $(V,E,F,c)=(7,5,1,2)$ で $V-E+F=3=1+c$。二つの木を離しても外面は一つである。
演習3。 $K_{3,3}$ に一辺を分割する次数2頂点を一つ加えたグラフが、式 (3) だけでは非平面と判定できないことを確かめよ。
解答。 新しいグラフは $V=7,E=10$ で $10\le3\cdot7-6=15$。ただし分割した辺を縮めて元に戻せば $K_{3,3}$ が得られるので、この描画は平面的にならない。式 (3) の逆は成り立たない。
演習4。 正方形の境界上に $a,b,c,d$ をこの巡回順に取る。$a$–$b$ と $c$–$d$ を正方形の同じ内側で、交差しない折れ線で結ぶ例を説明せよ。
解答。 $a$–$b$ をその間の短い境界弧に近い内側の折れ線で結び、$c$–$d$ も離れた境界弧に近い内側の折れ線で結ぶ。二本を十分細く離して選べば交わらない。端点は交互順ではないので定理に反しない。
演習5。 平面グラフの閉路 $C$ 上に $a,c,b,d$ がこの順にあり、内部頂点を共有しない二本の道がそれぞれ $a$–$b$ と $c$–$d$ を結ぶ。両道を閉路の同じ側へ描けない理由を述べよ。
解答。 同じ側で、かつ各道の内部が $C$ と交わらなければ交互端点定理により二道が交わる。内部頂点を共有しないので交点は辺の内部で起こり、平面描画に反する。従ってそのような同じ側の描画はできない。