双対グラフ
有向平面グラフの双対グラフは、各双対辺を対応する主辺から時計回りに90°回転させることによって、同様に指向させることができる。ただしこれは厳密に言えば双対ではない。なぜならば、グラフGから出発し、双対を二回とったとき、G自体に戻らず、Gの転置グラフ(Gの全てのエッジを反転させたグラフ)と同型なグラフになるからである。この定義の双対では、双対を4回取ると元のグラフに戻る。
木構造において、頂点の数Vと辺の数Eは、E = (V − 1) という関係をもつ。このことは次のようにして分かる。木構造は一つの頂点から初めて、新しい頂点と辺を加えていくことで作ることができる。この操作のはじめはE = 0,V = 1であり、その後E,Vが同数ずつ増えていく。このことから上式が成り立つことがわかる。
いま、グラフGについてその全域木Sが与えられたとする。Sの辺の数をESとすると、ES = (V − 1) が成り立つ。また~S*の辺の数をE~S*とすると、~S*はG* の全域木であるため、G*の頂点の数、すなわちGの面の数Fについて同様な関係 E~S* = (F − 1)が成り立つ。Sの辺の数と~Sの辺の数を足すとGの辺の数に等しく、また~Sの各辺は~S*の各辺に一対一に対応するため、
E = (V − 1) + (F − 1)
が成り立つ。これはオイラーの公式に他ならない。Duncan Sommervilleによると、オイラーの公式のこの証明はK. G. C. Von Staudtの Geometrie der Lage(Nürnberg, 1847)による。
非平面表面埋め込みでは、全域木と相補的な双対辺は元のグラフの全域木とはならない。そのかわり、これらは元のグラフの双対の全域木と少数の余分な辺を合わせた集合となる。このとき、余分な辺の数は、グラフが埋め込まれている曲面の種数によって決まる。この余分な辺は全域木に含まれる経路と合わせて用いることで、曲面の基本群を生成できる。
閉路グラフの双対の例から明らかなように、単純グラフの双対は単純であるとは限らず、自己ループ(両方の端点が同じ頂点にある辺)や同じ2つの頂点を結ぶ複数の辺がある場合がる。カット-サイクルの双対性の特別な場合として、平面グラフの橋はその双対グラフの自己ループと一対一に対応している。同じ理由で、双対多重グラフ内の一対の平行な辺(つまり、長さ2のサイクル)は、主グラフ内の2辺のカットセット(削除されるとグラフが切断される一対の辺)に対応する。したがって、平面グラフが単純である条件はその双対が1辺または2辺のカットセットを持たない場合に限る。つまり、3辺接続となる。単純平面グラフの双対が単純な場合、これは3辺連結単純グラフとなる。このクラスのグラフは、3頂点結合単純平面グラフを含むが、必ずしもそうではなく、たとえば、自己双対グラフを示す図は3辺接続だが(したがって、その双対は単純である)が、3頂点接続ではない。
連結グラフGの代数的双対Gは、GおよびGが同じ辺の組を持っていて、Gの全てのサイクル Gは、Gのカットであり、Gの全てのカットはGのサイクルであるようなグラフである。すべての平面グラフは代数双対を持ち、これは一般的に一意ではない(平面埋め込みによって定義される双対は一意となる)。Hassler Whitneyによる Whitneyの平面性の基準で解決されたように、この逆もまた真である。
連結グラフGは代数双対をもつ場合に限り、平面グラフである。
同じ事実はマトロイドの理論でも表現できる。MがグラフGのグラフィックマトロイドである場合、グラフGもしGの代数デュアルでありGのグラフィックマトロイドがある場合にのみ、デュアルマトロイド Mの。その場合、Whitneyの平面性基準は、グラフィックマトロイドM 双対マトロイドは、それ自体がM基礎となるグラフGが平面である場合に限り、それ自体がグラフィックマトロイドであると述べると言い換えることができる。Gが平面ならば、双対マトロイドはG双対グラフのグラフィックマトロイドである。
2つの多面体が双対であるときはそのグラフもまた双対となる。たとえば、正多面体において、立方体と正八面体、正二十面体と正十二面体、正四面体とそれ自身は、互いに双対の関係にある。多面体の双対性は、より高次元のポリトープの双対性に拡張することもできるが、三次元の場合とは異なり、グラフ理論的な双対性との明確な関連性を持っていない。
平面グラフの双対グラフがそれ自身と同型のとき、このグラフ自己双対と呼ばれる。車輪グラフは、自己双対多面体(角錐)に対応する自己双対グラフである。また、対応する多面体が存在しないような自己双対グラフも存在する。Servatius & Christopher (1992)は、「接着」と「爆発」と2つの操作を使うことで与えられた平面グラフを含む自己双対グラフを構築することが可能であることを述べている。例えば、図の自己双対グラフは四面体とその双対との接着として構成することができる。
オイラーの公式から、n個の頂点を持つすべての自己双対グラフは、厳密に2n − 2個の辺を持つ。すべての単純自己双対平面グラフは、次数3の頂点を少なくとも4つ含み、すべての自己双対グラフの埋め込みは少なくとも4つの三角形面を持つ。