5-3 平面双対

二つの面 $F,H$ の内部に点 $x,y$ を取ります。平面上で $x$ から $y$ へ曲線を引き、頂点を通らず、各辺と横断的に有限回だけ交わるよう少しずらします。
曲線を $x$ からたどると、一つの辺を横切るたびに現在の面から隣の面へ移ります。横切ったprimal edgeに対応するdual edgeを順に並べれば、$F^*$ から $H^*$ へのdual walkが得られます。walkから閉じた回り道を消せばpathが得られるので、$G^*$ は連結です。□

最初の二等式は構成そのものです。各primal頂点 $v$ の十分小さい円板を取ると、その境界を横切るdual edgeは $v$ に接続するprimal edgeの間を通り、円板の内部はdual graphの一つの面になります。異なるprimal頂点には互いに交わらない円板を取れます。
逆にdual graphの面から一点を選び、dual edgeを越えずに動ける領域を調べると、領域はちょうど一つのprimal頂点の周囲です。従ってdualの面とprimalの頂点が一対一に対応します。
dualのdualでは、この面に対応する頂点を元の $v$ と同一視できます。また $e^*$ を横切るdual-dual edgeは元の $e$ と同じ両端を結びます。よって埋め込みを保つ自然な同型 $(G^*)^*\cong G$ が得られます。□

2と3の同値はdualの定義です。
$e$ がbridgeでないなら、「切断点・橋・ブロック」のbridge特徴づけにより $e$ を含むcycle $C$ があります。polygonal Jordan曲線定理により、plane graph上のcycleは平面を内側と外側に分けます。$e$ の二側はそれぞれ異なる側にあるので、異なる面に属します。従って2ではありません。
逆に $e$ がbridgeなら、$G-e$ の二成分を $A,B$ とします。$e$ の近くで一方の側から他方の側へ回り込むとき、$A$ と $B$ を結ぶ別の辺はありません。したがって $e$ の両側の局所領域は外側を回る同じ面の中でつながり、両側は同じ面です。よって1なら2です。□

$G^*$ に前補題を適用すると、$e^*$ がbridgeであることは $(e^*)^*$ がloopであることと同値です。$(G^*)^*\cong G$ のもとで $(e^*)^*$ は $e$ に対応します。□

$C$ をplane graph上のcycleとします。対応する単純閉曲線により、面は内側の面集合 $\mathcal I$ と外側の面集合 $\mathcal O$ に分かれます。内外を結ぶdual edgeは、閉曲線を横切る $e^*$、すなわち $e\in C$ に対応するものだけです。従って
$$ C^*=\delta_{G^*}(\mathcal I). $$
cutとして削除する辺集合から一つの $e^*$ だけを除けば、その残した $e^*$ を通って内外を行き来できます。内側だけ、外側だけでは前節と同じ曲線横断の議論によりdual walkを作れるので、それぞれの側は連結です。従って $C^*$ のどの辺も分離に必要であり、$C^*$ はbondです。
逆に $C^*$ が $G^*$ のbondとします。bondはとくにdual cutです。各primal頂点の周囲で、bondが分ける二つのdual頂点群を巡回順に読むと、群が切り替わる回数は偶数です。従って対応するprimal辺集合 $C$ は全頂点を偶次数にする非空部分graphを作ります。
この部分graphで同じ辺を二度使わないmaximal trailを取ると、偶数次数性により終点は始点と一致し、閉trailになります。その中の最初の反復区間から、あるcycle $C_0\subseteq C$ が得られます。すでに証明した向きから $C_0^*$ は $G^*$ のbondであり、
$$ C_0^*\subseteq C^* $$
です。$C^*$ はcutとして極小なので $C_0^*=C^*$、従って $C_0=C$ です。よって $C$ 自身がcycleです。
最後の主張は、証明済みの同値を $G^*$ に適用し、$(G^*)^*\cong G$ と同一視すれば得られます。□

primal頂点 $v$ の周囲を小さく一周し、$v$ に接続する辺の間に現れる面を巡回順に読みます。面が $\mathcal A$ に属するか属さないかを0と1で記録すると、$D$ の辺は0から1または1から0へ切り替わる場所にちょうど対応します。
円を一周して出発点へ戻るので、0と1の切替回数は偶数です。これは $v$ における $D$ の次数が偶数であることを意味します。全ての $v$ で同じなので結論を得ます。□

辺をもつ頂点から出発し、同じ辺を二度使わないtrailを、延長できなくなるまで伸ばします。有限graphなのでこのmaximal trailは有限です。
終点が始点と異なるとします。終点ではtrailに使われた接続辺の本数が奇数です。しかし終点の全次数は偶数なので、まだ使っていない接続辺が少なくとも一本あり、trailを延長できて矛盾します。従ってtrailは閉じています。閉trailの頂点列で最初に生じる反復区間を取ればcycleが得られます。loopがあれば、それ自体を長さ1のcycleと数えます。□

まず $T$ を $G$ のspanning treeとします。$n=|V(G)|,m=|E(G)|,f=|\mathcal F(G)|$ とすると、Euler公式と $|T|=n-1$ から
$$ |T^\perp|=m-(n-1)=f-1=|V(G^*)|-1. $$
$T^\perp$ が連結でないと仮定します。その一つ以上、全て未満の連結成分の頂点を集めて $\mathcal A$ とします。dual cut $\delta_{G^*}(\mathcal A)$ には $T^\perp$ の辺が一本もありません。従ってこのcutに対応するprimal辺は全て $T$ に属します。
cutは空でありません。実際、$G^*$ は連結なので、非自明な $\mathcal A$ と補集合の間には辺があります。前二補題により、対応する非空なprimal辺集合はcycleを含みます。しかしそれらは全てtree $T$ の辺であり、$T$ がacyclicであることに反します。従って $T^\perp$ は連結です。頂点数より一本少ない辺をもつ連結graphなのでtreeです。
逆向きは、$G^*$ に今の向きを適用します。$T^\perp$ の補dual辺は、$(G^*)^*\cong G$ のもとでちょうど $T$ です。□

全辺重みの和を
$$ W=\sum_{e\in E(G)}w(e) $$
とします。spanning-tree dualityにより、$G$ のspanning tree $T$ と $G^*$ のspanning tree $T^\perp$ は全単射に対応します。しかも
$$ w^*(T^\perp) =\sum_{e\notin T}w(e) =W-w(T). $$
右辺の $W$ は $T$ に依存しません。従って $w(T)$ を最小にすることと $w^*(T^\perp)$ を最大にすることは同値です。□

2と3はdual頂点がprimal面であることから同値です。
1を仮定します。$G^*$ に奇cycleがあると、その辺集合はcycle--bond dualityにより $G$ のbond $\delta(S)$ に対応します。一方、$G$ の $S$ 内の次数を足すと
$$ \sum_{v\in S}\deg(v)=2|E(S)|+|\delta(S)|. $$
左辺と第一項は偶数なので、全てのcutの大きさは偶数です。これは奇cycleに対応するbondが奇数本であることに反します。従って $G^*$ に奇cycleはなく、「グラフ彩色」の特徴づけによりbipartiteです。
逆に $G^*$ がbipartiteとします。primal頂点 $v$ の周りを小さく一周すると、$v$ に接続する各辺を一度ずつ横切るdual closed walkが得られ、その長さはloopを接続回数に従って数えて $\deg(v)$ です。bipartite graphのclosed walkは一歩ごとに二つの部を交互に移るため長さが偶数です。従って全ての $v$ で $\deg(v)$ は偶数です。□

面は内面と外面の二つなのでdual頂点は2個です。四本の各辺は内面と外面を隔てるため、各dual edgeはこの二頂点を結びます。従ってdualは二頂点間に4本の平行辺をもつmultigraphで、両頂点の次数は4です。□

treeは $n-1$ 辺をもち、Euler公式から面数は
$$ f=2-n+(n-1)=1 $$
です。従ってdualは一頂点と $n-1$ 本のloopからなります。treeの全辺はbridgeであり、それぞれのdualがloopになっているので双対性を直接確認できます。□

Euler公式から
$$ f=2-n+m=2-8+12=6. $$
従って $G^*$ は頂点数6、辺数12、面数8です。$G$ では $8-12+6=2$、$G^*$ では $6-12+8=2$ となり、どちらもEuler公式を満たします。□

primal spanning treeは $n-1=5$ 辺です。補辺は $9-5=4$ 本です。一方、Euler公式から面数は
$$ f=2-6+9=5 $$
なので、dual spanning treeの辺数は $f-1=4$ です。補辺数と一致します。spanning-tree dualityにより、これら4本は実際にdualを連結かつacyclicにします。□

補dual treeの重みは
$$ 40-13=27 $$
です。任意のprimal spanning tree $S$ とその補dual tree $S^\perp$ について
$$ w(S^\perp)=40-w(S) $$
です。minimum treeの重み13は全ての $w(S)$ 以下なので、27は全ての $w(S^\perp)$ 以上です。従って補dual treeはmaximum-weight spanning treeです。□

最初の次数列では全頂点次数が偶数なので、Eulerian--bipartite dualityによりdualはbipartiteです。dualの二部を二色と見れば、辺を共有するprimal面は異なる色になり、面のproper二色塗りが得られます。
二番目には奇次数頂点が二つあります。したがって「全次数が偶数」という十分必要条件を満たさず、実際dualはbipartiteではありません。よって面のproper二色塗りはできません。単に次数和が偶数であることだけでは足りず、各頂点の次数が偶数である必要があります。□