$G$を平面グラフとする。 $G$の各面の内部に点をひとつずつ選び、これらの点の全体を$V^*=V(G^*)$とする。 $u^*,v^*\in V^*$に対して、 $u^*$の属する面と$v^*$の属する面が$G$の辺$e$で接するとき、 $u^*$と$v^*$を、$G$の$e$以外の辺とは共有点をもたない曲線$e^*$で結ぶ。 このようにして得られる曲線の全体を、$E^*=E(G^*)$とする。
$G^*:=(V^*,E^*)$は(適当な解釈の下で)グラフの公理をみたす。 $G^*$を、$G$の幾何学的双対(geometric dual)と呼ぶ。
$G^*$の定義は$V^*$や$E^*$の元の選び方によらない。 つまり別の取り方をしても同型なグラフを得ることに注意する。
$E^*$の2元が交差しないように選ぶことができるのは明らか。 つまり$G^*$は平面グラフになる。 従ってその幾何学的双対$G^{**}$を構成することができる。
この$G^{**}$に関して、次の定理が成り立つ。
証明
幾何学的双対の定義から、明らかである。
\hfill(証明終了)
ここで 平面グラフの閉路とカットセットの間の双対的な関係についての定理を与える。
証明
$C$を$G$の辺の集合、$C^*$を対応する$G^*$の辺の集合とする。
\[ C\textop{が$G$の閉路}\iff C^*\textop{が$G^*$のカットセット} \]
を示す。
(i) $C$が閉路 $\Rightarrow \;C^*$が非連結化集合。
$C$の内部にある$G^*$の頂点の全体、辺の全体をそれぞれ$V^*_1$、 $E^*_1$とする。 また外部にある$G^*$の頂点の全体、辺の全体をそれぞれ$V^*_2$、 $E^*_2$とする。 $C$が閉路なので
\[ V^*_1\ne\emptyset,\;V^*_2\ne\emptyset,\; V(G^*)=V^*_1\coprod V^*_2,\; E(G^*)\setminus C^*=E^*_1\coprod E^*_2 \]であり、さらに$V^*_1$の頂点に接続するのは$E^*_1$の辺のみ、 $V^*_2$の頂点に接続するのは$E^*_2$の辺のみである。 従って$G^*_1:=(V^*_1,E^*_1)$と $G^*_2:=(V^*_2,E^*_2)$は$G^*$の部分グラフをなし、
\[ G^*\setminus C^*=G^*_1\union G^*_2. \]よって$G^*\setminus C^*$は非連結、つまり$C^*$は$G^*$の非連結化集合になる。
(ii) $C^*$がカットセット $\Rightarrow \;C$は閉路。
対偶を示す。
もし閉路$C_1$が$C$の真部分集合ならば、 $C_1$に対応する$G^*$の辺の集合$C^*_1$は、 (i)によって$G^*$の非連結化集合であって、 しかも$C^*$の真部分集合である。 従って$C^*$は極小非連結化集合ではあり得ない。
$C$が閉路を全く含まない場合、明かに$G^*$の任意の頂点は、 $G$の無限面に対応する頂点と、 $C$の辺と交差しない散歩道で結ぶことができる。
従って$G^*\setminus C^*$は連結である。 つまり$C^*$は非連結化集合ではない。 よってカットセットでもない。
(iii) $C$が閉路 $\Rightarrow \;C^*$はカットセット。
(i)によって、$C^*$は非連結化集合である。 従ってカットセット$C^*_1$を含む。 (ii)によって、$C^*_1$に対応する$G$の辺の集合$C_1$は閉路であって、 しかも$C_1\subset C$である。 閉路が他の閉路の真部分集合になることはあり得ないから、 $C_1=C$である。
よって$C^*_1=C^*$。 つまり$C^*$はカットセット。
\hfill(証明終了)
証明
$G^*$に上の定理を適用すると、 $G^*$の辺のある集合$C^*$が$G^*$の閉路であるための必要十分条件は、 それに対応する$G^{**}$の辺の集合$C^{**}$が$G^{**}$のカットセットになることである。
$G^{**}$が$G$に同型だから、 $G$の辺のある集合$C$が$G$のカットセットであるための必要十分条件は、 それに対応する$G^*$の辺の集合$C^*$が$G^*$の閉路になることである。
\hfill(証明終了)
グラフ$G$と$G^*$に対して、 $G$の辺集合と$G^*$の辺集合の間に一対一対応があり、 $G$の辺の集合が閉路になるための必要十分条件が、 対応する$G^*$の辺の集合がカットセットになることであるならば、 $G^*$は$G$の抽象的双対(abstract dual)であるという。
上の定理によって、 $G^*$が連結平面グラフ$G$の幾何学的双対ならば、 $G^*$は$G$の抽象的双対でもある。
また次の定理が成り立つ。
証明
$G$の辺の集合$C$と、対応する$G^*$の辺の集合$C^*$に対して、
\[ \text{$C^*$が$G^*$の閉路}\iff \text{$C$が$G$のカットセット} \]
を示せばよい。
($\Leftarrow$)
閉路とカットセットの定理より、 $C$は$G$のどの閉路とも偶数本の共通辺をもつので、 $C$に対応する$C^*$は$G^*$のどのカットセットとも 偶数本の共通辺をもつ。
従って閉路とカットセットの定理より、 $C^*$は互いに素な閉路に分割できる。 このとき$C^*$は$G^*$のひとつの閉路であるか、 あるいは$G^*$の2つの以上の閉路の辺が素な和である。
$C^*$が素な2つ以上の閉路の和として
\[ C^*=C^*_1\coprod C^*_2\coprod \ldots \coprod C^*_n \]と表わされていると仮定してみる。 $C^*_1,C^*_2,\ldots,C^*_n$に対応する$G$の辺の集合をそれぞれ
\[ C_1,C_2,\ldots,C_n \]とする。
双対の定義により
\[ C=C_1\coprod C_2\coprod \ldots \coprod C_n \]であって、しかも$C_1,\,C_2,\ldots,C_n$はみなカットセット。 これはカットセットの極小性と矛盾する。
従って$C^*$はひとつの閉路である。
($\Rightarrow$)
$G^*$の任意のカットセットは、 閉路とカットセットの定理により、 $C^*$と偶数本の共通辺をもつ。 従って抽象的双対の定義により、 $G$の任意の閉路は$C$と偶数本の共通辺をもつ。
このとき$C$が非連結化集合であること、 つまり$G\setminus C$が連結ではないことを示す。
$e$を$C$に属する辺のひとつとする。 $e$がループなら、$e$のみで閉路をなし、 しかも$C$との共通辺は$e$ 1本のみとなり、上に述べたことと矛盾する。 従って辺$e$はループではない。 よって$e$に接続する頂点が2個ある。 それらを$u$と$v$とする。
もし$C$が非連結化集合でないならば、$G$で同じ成分に属する頂点は、 $G\setminus C$でも同じ成分に属する。 従って頂点$u$と$v$は$G\setminus C$の同じ成分に属する。 よって$u$と$v$を結ぶ$G\setminus C$の道が存在する。 その道と辺$e$をつなげれば$G$の閉路が得られるが、 この閉路と$C$の共通辺は$e$ 1本のみとなって、 やはり上に述べたことと矛盾する。
従って$C$は非連結化集合でなければならない。 よって$C$はカットセット$K$を含む。
$K$に対応する$G^*$の辺の集合を$K^*$とすると、 $K^*\subset C^*$であって、しかも前半で示したことにより、 $K^*$は閉路である。 $C^*$も閉路なので$K^*=C^*$でなければならない。 従って$K=C$である。
つまり$C$は$G$のカットセット。
\hfill(証明終了)