双対グラフ
概要
双対グラフ（dual graph）とは、平面に描いたグラフ $G$ の各面を頂点とし、$G$ の各辺 $e$ に対してその両側の面を結ぶ辺 $e^{*}$ を置いた多重グラフ $G^{*}$ であり、橋はループに対応し、面の次数の総和は辺数の $2$ 倍になる。辺の集合 $E$ が $G$ の閉路であることと $E^{*}$ が $G^{*}$ のボンド（極小なカット）であることは同値である。ここから、全域木の補集合が双対の全域木になること、すべての頂点の次数が偶数であることと双対が二部グラフであることの同値が従う。地図の塗り分けは双対の頂点彩色になるが、双対は描き方に依存し、同じグラフの別の描画から同型でない双対が得られることがある。
平面に描いたグラフの各面に 1 つずつ点を置き、元のグラフの各辺を 1 回だけ横切るように、その辺をはさむ 2 つの面の点を結ぶ。こうしてできるグラフが双対グラフである。地図の国を頂点、国境を辺とみなすと、国の塗り分けは双対グラフの頂点彩色になり、四色定理 は平面グラフの彩色の問題に言い換えられる。
双対をとると、閉路と「極小な切断」（ボンド）が入れ替わる。平面グラフ図 $G$ の辺の集合 $E$ が閉路であることと、対応する双対の辺の集合 $E^{*}$ が双対グラフのボンドであることは同値である（thm-dg-cycle-bond）。ここから、全域木の補集合が双対の全域木になること、すべての次数が偶数であることと双対が二部グラフであることの同値などが従う。双対グラフは抽象グラフではなく平面への描き方に依存する。同じグラフの別の描き方から同型でない双対が得られることがある（ex-dg-counterexamples）。
なお、代数曲線の配置に対して、曲線を頂点とし交わる曲線どうしを結んだグラフも双対グラフと呼ばれる（Du Val特異点 の記事の定理「Du Val特異点の双対グラフ」）。この記事で扱うのは平面グラフの双対であり、それとは別の概念である。
定義
平面グラフ図の約束は Kuratowskiの定理 の記事の定義「平面への描画」に従う。すなわち、有限な単純グラフ $G$ の頂点を平面 $\mathbb R^2$ の相異なる点、辺を両端の点を結ぶ折れ線の弧で表し、辺の弧の内部はどの頂点の点も他の辺の点も含まないとする。描画を固定したものを平面グラフ図といい、同じ記号 $G$ で点集合（頂点と辺の和集合）も表す。$\mathbb R^2\setminus G$ の連結成分を $G$ の面といい、面の全体を $F(G)$ と書く。部分グラフ $H\subset G$ も描画を制限して平面グラフ図とみなす。
平面グラフ図 $G$ について次の事実を用いる（Die25 Lemma 4.2.1・Lemma 4.2.2 とその証明、pp. 97–98）。
- (T1) $f\in F(G)$ と部分グラフ $H\subset G$ について、$f$ は $H$ のある面に含まれる。
- (T2) 辺 $e$ の弧の内部の点 $x$ で、$e$ を作る線分の折れ点でないものをとると、そのまわりの十分小さい開円板 $D$ は、$G$ と $e$ の 1 本の線分でだけ交わる。$D$ から $e$ を除いた 2 つの開半円板はそれぞれ $G$ のある面 $f_1,f_2$ に含まれ、境界が $e$ と交わる面は $f_1,f_2$ だけである。$e$ が $G$ のある閉路の上にあれば $f_1\neq f_2$ であり、どの閉路の上にもなければ $f_1=f_2$ である。
(T2) で $D$ を小さくとれば、$e$ を含む部分グラフ $H$ についても同じ円板が使える。とくに、$e$ が $H$ の閉路の上にあれば、2 つの半円板は $H$ の異なる面に含まれる。
(T2) の $f_1,f_2$ を、$e$ の両側の面という。$f_1=f_2$ となる辺は、取り除くと連結成分が増える辺（橋）にほかならない。
平面グラフ図 $G$ の 双対グラフ（dual graph）$G^{*}$ とは、頂点の集合を $F(G)$ とし、$G$ の各辺 $e$ に対して辺 $e^{*}$ を 1 本ずつ置き、$e^{*}$ の両端を $e$ の両側の面とした多重グラフ（ループと平行辺を許す）である。$e$ の両側の面が一致するとき、$e^{*}$ はその面でのループである。辺の集合 $E\subset E(G)$ に対して $E^{*}:=\{e^{*}\mid e\in E\}$ と書く。
面 $f$ の次数 $d(f)$ を、$f$ を両側の面にもつ辺の本数とする。ただし両側がともに $f$ である辺（橋）は $2$ 本と数える。次数を $G^{*}$ で数えると、ループは $2$ と数えるので、$d(f)$ は $G^{*}$ での頂点 $f$ の次数に等しい。
$G^{*}$ を平面に描くには、各面 $f$ の中に点を 1 つ置き、各辺 $e$ をちょうど 1 回横切る弧で両側の面の点を結べばよい。これが辺の交わらない描画になること、さらに $G$ が連結なら $G^{*}$ のこの描画の双対が $G$ と同型になることが知られている（Die25 §4.6、pp. 114–115。BM76 §9.2、pp. 140–142 と Exercise 9.2.4。この記事では証明しない）。以下の議論は抽象的な多重グラフ $G^{*}$ だけを使い、この事実には依存しない。
次に、閉路と対になる辺の集合を定める（Die25 §1.9、p. 24）。多重グラフ $X$ の頂点の集合を空でない 2 つの集合 $S,S'$ に分けたとき、一方の端が $S$、他方の端が $S'$ にある辺の集合 $E_X(S,S')$ を $X$ のカットという。ループはどのカットにも属さない。空でないカットで、真部分集合に空でないカットを含まないものをボンドという。
連結な多重グラフ $X$ のカット $E_X(S,S')$ について、$S$ と $S'$ がそれぞれ連結な部分グラフを誘導するなら、$E_X(S,S')$ はボンドである。
$X$ は連結なので $E_X(S,S')\neq\emptyset$ である。空でないカット $E_X(T,T')\subset E_X(S,S')$ をとる。$X[S]$ の辺は $E_X(S,S')$ に属さないので $E_X(T,T')$ にも属さず、両端は $T$ と $T'$ の同じ側にある。$X[S]$ は連結なので $S$ 全体が $T$ か $T'$ の一方に含まれ、$S'$ も同様である。$S$ と $S'$ が同じ側に入ると他方の側が空になるので、$\{T,T'\}=\{S,S'\}$ であり、2 つのカットは一致する。$\square$
例
- 木：$G$ が木なら面は 1 つで、すべての辺は橋である。$G^{*}$ は 1 頂点に $\lvert E(G)\rvert$ 本のループを付けた多重グラフである。
- 閉路：$G=C_n$（$n\ge3$）の面は内側と外側の 2 つで（多角形のJordan曲線定理）、どの辺も両者を隔てる。$G^{*}$ は 2 頂点を $n$ 本の平行辺で結んだ多重グラフであり、単純グラフにならない。
- $K_4$：平面グラフ の記事の例「完全グラフ$K_4$」の描画では、面は 3 つの内側の三角形と外側の三角形の 4 つで、どの 2 つの面もちょうど 1 本の辺を共有する。よって $K_4^{*}\cong K_4$ である。
- 立方体と正八面体：立方体の辺の描画（内側の正方形を外側の正方形の中に置き、対応する頂点を結ぶ）の面は 6 つの四角形で、各面はほかの 4 つの面と 1 本ずつ辺を共有し、向かい合う面とは辺を共有しない。$G^{*}$ は 6 頂点の各頂点が向かい合う 1 頂点以外のすべてと隣接するグラフ、すなわち正八面体のグラフである（正多面体）。
- 車輪：閉路の中央に 1 頂点を置いて閉路のすべての頂点と結んだ 車輪グラフ $W_n$ は、外周を正多角形に、中央の頂点をその中心に置いて描くと、その双対が $W_n$ と同型になる（車輪グラフ の記事の定理「車輪グラフの自己双対性」）。
1 と 2 のように、元のグラフが単純でも双対には平行辺やループが現れる。平面グラフ の記事の末尾で注意されているとおり、双対グラフを単純グラフと決めつけてはならない。
性質
頂点・辺・次数
平面グラフ図 $G$ の辺数を $m$ とする。$G^{*}$ の頂点数は $G$ の面の数 $\lvert F(G)\rvert$、辺数は $m$ であり、頂点 $f$ の次数は面の次数 $d(f)$ である。したがって
$$
\sum_{f\in F(G)}d(f)=2m
$$
が成り立つ。また、辺 $e$ が $G$ の橋であることと、$e^{*}$ がループであることは同値である。
頂点と辺の個数は def-dg-dual からただちに分かる。次数の主張は定義の直後に述べたとおりである。和の式は $G^{*}$ についての次数(グラフ) の記事の定理「次数の総和と辺数」（ループは次数に $2$ を加える）である。最後の主張は、(T2) により $e$ の両側の面が一致することと $e$ がどの閉路の上にもないことが同値であり、どの閉路の上にもない辺が橋であることによる。$\square$
和の式は BM76 Theorem 9.4（p. 142）である。平面グラフ の記事の系「単純平面グラフの辺数の上界」の証明で使われる数え上げは、双対グラフの握手補題として読める。
部分グラフの面と双対の連結成分
主定理の鍵は、辺を何本か除いたときに面がどうつながるかを、双対グラフの連結成分で数えられることである。
平面グラフ図 $G$ と辺の集合 $E\subset E(G)$ をとり、$G$ の頂点をすべて残して辺を $E$ だけにした部分グラフを $H:=(V(G),E)$ とする。$G$ の 2 つの面 $f,g$ について、次の 2 条件は同値である。
- $f$ と $g$ は $H$ の同じ面に含まれる。
- $f$ と $g$ は $G^{*}-E^{*}$ の同じ連結成分に属する。
さらに、$H$ の面の個数は $G^{*}-E^{*}$ の連結成分の個数に等しい。
(T1) により $G$ の各面 $f$ は $H$ のただ 1 つの面に含まれる。それを $\varphi(f)$ と書く。
2 ⇒ 1．$e\notin E$ とし、$e^{*}$ の両端を $f,g$ とする。(T2) の円板 $D$ の中で、$e$ の内部の点 $x$ を通り $e$ を横切る短い線分は、$f$ の点と $g$ の点を結び、$G$ とは $x$ だけで交わる。$x$ は $H$ の点でない（$e\notin E$ で、$x$ は頂点でも他の辺の点でもない）ので、この線分は $H$ と交わらず、$\varphi(f)=\varphi(g)$ である。$G^{*}-E^{*}$ の歩道に沿ってこれを繰り返せば 2 ⇒ 1 を得る。よって $\varphi$ は、$G^{*}-E^{*}$ の連結成分の全体から $H$ の面の全体への写像 $\Phi$ を定める。
$\Phi$ は全射．$H$ の面 $O$ は空でない開集合である。$G$ は有限個の点と線分の和集合で開円板を含まないので、$O$ は $G$ に属さない点を含む。その点を含む $G$ の面 $f$ について $\varphi(f)$ は $O$ と交わるので、$\varphi(f)=O$ である。
個数が等しい．$G^{*}-E^{*}$ の連結成分の個数を $k(E)$、$H$ の面の個数を $h(E)$ とする。全射性から $k(E)\ge h(E)$ である。$\lvert E(G)\setminus E\rvert$ についての帰納法で $k(E)=h(E)$ を示す。$E=E(G)$ なら、$G^{*}-E^{*}$ は辺をもたないので $k=\lvert F(G)\rvert$、$H=G$ なので $h=\lvert F(G)\rvert$ である。$E\ne E(G)$ とし、$e\in E(G)\setminus E$、$E^{+}:=E\cup\{e\}$、$H^{+}:=(V(G),E^{+})$ として $k(E^{+})=h(E^{+})$ を仮定する。$G^{*}-E^{*}$ は $G^{*}-(E^{+})^{*}$ に辺 $e^{*}$ を加えたものなので、$k(E)$ は $k(E^{+})$ か $k(E^{+})-1$ である。$H$ と $H^{+}$ に 平面グラフ の記事の命題「連結成分の個数を入れたEulerの公式」を使う。
- $e$ が $H^{+}$ のある閉路の上にあるとき、$H$ と $H^{+}$ の連結成分の個数は等しいので $h(E)=h(E^{+})-1$ である。一方 (T2) を $H^{+}$ に使うと、$x$ のまわりの 2 つの半円板は $H^{+}$ の異なる面に含まれる。半円板は $e^{*}$ の両端の面 $f,g$ に含まれるので $f,g$ は $H^{+}$ の異なる面に含まれ、2 ⇒ 1（$E^{+}$ について）の対偶により $G^{*}-(E^{+})^{*}$ の異なる連結成分に属する。よって $k(E)=k(E^{+})-1=h(E^{+})-1=h(E)$ である。
- $e$ が $H^{+}$ のどの閉路の上にもないとき、$e$ は $H^{+}$ の橋なので $H$ の連結成分は 1 つ増え、$h(E)=h(E^{+})$ である。$h(E)\le k(E)\le k(E^{+})=h(E^{+})=h(E)$ から $k(E)=h(E)$ である。
1 ⇒ 2．$\Phi$ は個数の等しい有限集合の間の全射なので単射である。$\varphi(f)=\varphi(g)$ なら $f$ と $g$ の属する連結成分は $\Phi$ で同じ面に移るので一致する。$\square$
$E=\emptyset$ とすると $H$ は辺のないグラフで、面は $\mathbb R^2$ から有限個の点を除いた 1 つだけである。よって次が分かる。
平面グラフ図 $G$ の双対グラフ $G^{*}$ は連結である。
閉路とボンドの対応
平面グラフ図 $G$ と辺の集合 $E\subset E(G)$ について、次の 2 条件は同値である。
- $E$ は $G$ のある閉路の辺の集合である。
- $E^{*}$ は $G^{*}$ のボンドである。
$n:=\lvert V(G)\rvert$ とし、$H:=(V(G),E)$ とおく。
1 ⇒ 2．$E$ を閉路 $C$ の辺の集合とする。$H$ は $C$ と $n-\lvert E\rvert$ 個の孤立点からなり（閉路の頂点数と辺数は等しい）、連結成分は $1+n-\lvert E\rvert$ 個である。平面グラフ の記事の命題「連結成分の個数を入れたEulerの公式」により $H$ の面の数は $1+(1+n-\lvert E\rvert)-n+\lvert E\rvert=2$ である。lem-dg-components により $G^{*}-E^{*}$ の連結成分はちょうど 2 つで、その頂点の集合を $S,S'$ とする。$e\notin E$ なら $e^{*}$ は $G^{*}-E^{*}$ の辺なので、両端は同じ成分にある。$e\in E$ なら $e$ は $H$ の閉路 $C$ の上にあるので、(T2) により $e$ の両側の $G$ の面は $H$ の異なる面に含まれ、lem-dg-components により異なる成分に属する。よって $E^{*}=E_{G^{*}}(S,S')$ である。$G^{*}[S]$ は $G^{*}-E^{*}$ の連結成分を含むので連結であり、$G^{*}[S']$ も同様である。cor-dg-connected と lem-dg-bond-sides により $E^{*}$ はボンドである。
2 ⇒ 1．$E^{*}=E_{G^{*}}(S,S')$ をボンドとする。$G^{*}-E^{*}$ には $S$ と $S'$ を結ぶ辺がないので、連結成分は 2 つ以上あり、lem-dg-components により $H$ の面も 2 つ以上ある。$H$ が閉路をもたなければ、$H$ は連結成分が $c$ 個の森で辺は $n-c$ 本（全域木 の記事の命題「木と森の辺の本数」）なので、面の数は $1+c-n+(n-c)=1$ となり矛盾する。よって $H$ は閉路 $C$ を含み、$E(C)\subset E$ である。1 ⇒ 2 により $E(C)^{*}$ はボンドで、$E(C)^{*}\subset E^{*}$ である。ボンド $E^{*}$ は真部分集合に空でないカットを含まないので $E(C)^{*}=E^{*}$、すなわち $E=E(C)$ である。$\square$
この定理は、連結な $G$ については Die25 Proposition 4.6.1（p. 115）に当たる。そこでは $G^{*}$ を平面に描いた双対として扱い、$G^{*}-E^{*}$ の道を平面上の弧と読み替えて証明している。上の証明は描かれた $G^{*}$ を使わず、面の個数を Euler の公式で数えることで同じ結論を得た。
全域木の補集合
$G$ を連結な平面グラフ図、$T$ を $G$ の全域木とする。$T$ に属さない辺の双対の集合 $(E(G)\setminus E(T))^{*}$ は、$G^{*}$ の全域木の辺の集合である。
$n:=\lvert V(G)\rvert$、$m:=\lvert E(G)\rvert$、$f:=\lvert F(G)\rvert$ とする。lem-dg-components を $E=E(T)$ に使う。$H=T$ は木なので、prf-dg-cycle-bond の後半と同じ計算で面は 1 つであり、$G^{*}-E(T)^{*}$ は連結である。このグラフは $G^{*}$ の頂点をすべてもち、辺の集合は $(E(G)\setminus E(T))^{*}$ である。その辺数は $m-(n-1)$ で、平面グラフ の記事の定理「Eulerの公式」により $f=2-n+m$ なので、$f-1$ に等しい。$f$ 頂点の連結なグラフで辺が $f-1$ 本のものは木である（全域木 の記事の命題「木の判定」）。$\square$
この系は BM76 Exercise 9.2.5（p. 143）の内容である。連結な平面グラフ図の辺は、全域木 $T$ の辺と、双対の全域木に対応する辺に分かれる。
閉路空間とカット空間
辺の集合を、対称差を和とする $\mathbb F_2$ 上のベクトル空間とみなす。$G$ の辺の集合 $D$ で、$(V(G),D)$ のすべての頂点の次数が偶数であるものの全体を $\mathcal C(G)$ と書く。これは互いに辺を共有しない閉路の和集合として書ける辺の集合の全体に等しい（Die25 Proposition 1.9.1、p. 24。空集合も含む）。多重グラフ $X$ のカットの全体に $\emptyset$ を加えたものを $\mathcal B(X)$ と書く。これは対称差で閉じ、そのどの元も互いに交わらないボンドの和集合である（Die25 Proposition 1.9.2、p. 24、Lemma 1.9.3、p. 25。多重グラフでも同じ証明が通ることは同書 p. 116 の脚注）。
平面グラフ図 $G$ について、次が成り立つ。
- $\{D^{*}\mid D\in\mathcal C(G)\}=\mathcal B(G^{*})$ である。
- $G$ のすべての頂点の次数が偶数であることと、$G^{*}$ が二部グラフであることは同値である。
1：$D\in\mathcal C(G)$ を互いに辺を共有しない閉路の和集合 $E(C_1)\cup\dots\cup E(C_k)$ と書く。thm-dg-cycle-bond により各 $E(C_i)^{*}$ はボンドで、それらは互いに交わらないので、$D^{*}$ はその対称差として $\mathcal B(G^{*})$ に属する。逆に $\mathcal B(G^{*})$ の元を互いに交わらないボンドの和集合 $B_1\cup\dots\cup B_k$ と書くと、thm-dg-cycle-bond により $B_i=E(C_i)^{*}$ となる閉路 $C_i$ があり、$C_i$ は互いに辺を共有しないので、$E(C_1)\cup\dots\cup E(C_k)\in\mathcal C(G)$ である。
2：$G^{*}$ が二部グラフであるとは、頂点の集合を 2 つに分けて（一方は空でもよい）すべての辺が 2 つの部分を結ぶようにできることである。ループはこれを妨げる。cor-dg-connected により $G^{*}$ は連結なので、辺があれば 2 つの部分はともに空でなく、$G^{*}$ が二部グラフであることは $E(G^{*})\in\mathcal B(G^{*})$ と同値である（辺がないときも $\emptyset\in\mathcal B(G^{*})$ で同値）。1 によりこれは $E(G)\in\mathcal C(G)$、すなわち $G$ のすべての頂点の次数が偶数であることと同値である。$\square$
2 の「すべての次数が偶数なら双対は二部グラフ」は、連結な $G$ について BM76 Exercise 9.2.3 (b)（p. 143）の主張である。連結な $G$ では、すべての次数が偶数であることは Euler 閉路をもつことと同値である（Euler閉路 の記事の定理「Euler の定理」）。たとえば正八面体のグラフはすべての頂点の次数が $4$ なので、その双対は二部グラフである（実際、8 つの三角形の面を頂点とする立方体のグラフになる）。
面の塗り分け
平面グラフ図 $G$ の面への色の割り当てで、どの辺についても両側の面の色が異なるものを、面の塗り分けという。
平面グラフ図 $G$ の面を $k$ 色で塗り分けることと、$G^{*}$ を $k$ 色で頂点彩色することは同じである。とくに $G$ が橋をもてば、面の塗り分けは存在しない。
面への色の割り当て $c$ は $G^{*}$ の頂点への色の割り当てであり、「辺 $e$ の両側の面の色が異なる」は「$e^{*}$ の両端の色が異なる」と同じである。$e$ が橋なら両側の面が一致し、$e^{*}$ はprop-dg-counts によりループなので、条件は満たされない。$\square$
$G^{*}$ が平面に描けるという引用の事実（def-dg-dual の後。この記事では証明しない）と 四色定理 を合わせると、橋をもたない平面グラフ図の面は 4 色で塗り分けられる。地図の国と国境が平面グラフ図の面と辺にあたる。
抽象的な双対と Whitney の定理
グラフ $G$ に対し、辺の集合が $E(G)$ と同じ多重グラフ $X$ で、$X$ のボンドがちょうど $G$ の閉路の辺の集合であるものを、$G$ の抽象的な双対という。thm-dg-cycle-bond は、平面グラフ図 $G$ の双対グラフ（$e$ と $e^{*}$ を同一視する）が抽象的な双対であることを示している。したがって平面グラフは抽象的な双対をもつ。逆に、抽象的な双対をもつグラフは平面グラフである。この同値は Whitney（1932 年）による（Die25 Theorem 4.6.3、p. 117。逆向きは MacLane の平面性の判定法 Die25 Theorem 4.5.1、p. 112 を使う。この記事では証明しない）。抽象的な双対の存在は、平面性判定 の一つの言い換えでもある。
条件を外したときの反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-dg-cycle-bond の「$E$ がちょうど閉路」（閉路を含む集合に広げる） | $K_4$ の三角形に別の 1 辺を加えた $E$ | $E^{*}$ がボンドであること |
| 描画を固定すること（抽象グラフだけを見る） | 2 頂点を長さ $2,2,3,3$ の 4 本の道で結んだグラフの 2 通りの描画 | 双対がグラフだけで決まること |
| $G$ の連結性（引用した $G^{**}\cong G$） | 離れた 2 つの三角形と、1 点を共有する 2 つの三角形 | $G^{**}\cong G$ |
| 橋をもたないこと | 2 つの三角形を 1 本の辺でつないだグラフ | 面の塗り分けが存在すること |
1 行目：$K_4$ を ex-dg-examples の 3 のように描き、外側の三角形の辺の集合を $T$、内側の頂点から出る辺の 1 本を $e$ とする。$E=T\cup\{e\}$ について、$E^{*}$ はボンド $T^{*}$ を真に含むので、それ自身がカットであっても極小でなく、ボンドではない。
2 行目：2 頂点 $x,y$ を、内部の頂点が互いに異なる長さ $2,2,3,3$ の道 $P_1,P_2,P_3,P_4$ で結んだグラフ $G$ は、頂点 $8$、辺 $10$ の連結な平面グラフで、どの描画でも面は Euler の公式により $4$ つである。$x$ のまわりに道を $P_1,P_2,P_3,P_4$ の順に並べて描くと、面は隣り合う 2 本の道で囲まれ、次数は $4,5,6,5$ である。$P_1,P_3,P_2,P_4$ の順に描くと、次数は $5,5,5,5$ である。橋はないので双対の頂点の次数は面の次数に等しく（prop-dg-counts）、2 つの双対は次数の並びが違うので同型でない。同じことを示す別の例が BM76 Figure 9.8（p. 142）にある。
3 行目：2 つの三角形を離して描いた図も、1 頂点を共有する 2 つの三角形の図も、面は 2 つの三角形の内側と外側の 3 つで、双対はどちらも、外側の面の頂点が残りの 2 頂点とそれぞれ 3 本の平行辺で結ばれた多重グラフである。元のグラフは頂点数が $6$ と $5$ で異なる。後者は連結で、前者は連結でない。前者について、$G^{*}$ を描いた図は頂点 $3$・辺 $6$ の連結な平面多重グラフなので、Euler の公式（BM76 Theorem 9.5、p. 143）により面は $2-3+6=5$ 個であり、$G^{**}$ は $5$ 頂点で $6$ 頂点の $G$ と同型でない。
4 行目：三角形 $abc$ と $def$ を辺 $cd$ で結ぶと、$cd$ は橋で、両側はともに外側の面である。prop-dg-face-coloring により面の塗り分けは存在しない。
補足
- 双対の双対：連結な $G$ では、$G^{*}$ を def-dg-dual の後に述べたように描くと、その双対は $G$ と同型になる（Die25 p. 115、BM76 Exercise 9.2.4、p. 143）。この記事の議論は抽象的な多重グラフ $G^{*}$ だけを使ったので、この事実には依存しない。
- 自己双対：$G^{*}\cong G$ となる平面グラフ図を自己双対という。辺数 $m$、頂点数 $n$ の自己双対な連結平面グラフ図では面の数も $n$ なので、Euler の公式から $m=2n-2$ である（BM76 Exercise 9.2.2、p. 142）。$K_4$ と車輪グラフがその例である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
