双対グラフ
特に、Gすべての異なる平面埋め込みに対して、すべての双対グラフは同型グラフィックマトロイドを持つ。
非平面曲面埋め込みの場合、平面双対とは異なり、双対グラフは一般に主グラフの代数双対ではない。そして、非平面グラフGについて、Gのグラフィックマトロイドの双対マトロイドは、グラフィックマトロイドそのものではない。しかし、それは依然として、サイクルがGのカットに対応するマトロイドであり、この意味では代数双対の一般化として考えることができる。
オイラー平面グラフと2部平面グラフの双対性は、二項マトロイド(平面グラフから派生したグラフィックマトロイドを含む)に拡張できる。二項マトロイドが2部である場合に限り、二項マトロイドはオイラー的である。ガースとエッジ接続性という2つの双対概念は、マトロイドガースによってマトロイド理論に統一される。平面グラフのグラフィックマトロイドのガースは、グラフのガースと同じである。また、双対マトロイドガース(双対のグラフィックマトロイド)はグラフのエッジ連結性である。
全域木は、グラフのすべての頂点を含む、連結された非巡回サブグラフとして定義できる。ここで、平面グラフGとその双対G*を考える。Gの全域木Sに対し、GのうちS に含まれないグラフを~Sとする。また、G*のうち~Sに対応するグラフを~S*とする。このとき~S*はG*の全域木となる。これは次のようにして分かる。Sはサイクルを持たないため、Gの各々の面を囲む辺のうち、少なくとも1つは~Sに含まれる。このことを双対の世界で言い直すと、G*の各頂点は必ず~S*がもつ辺により連結されるということになる。ここでもし~S*がサイクルを持つとすると、同様の議論によって、Gの頂点のうち少なくとも1つがSにより連結されないことになる。しかし、これはSが全域木であることと相容れないため、~S*はサイクルを持たない。よって、~S*はG*の全ての頂点を連結し、サイクルを持たない。すなわち~S*はG*の全域木である。
このことから、平面グラフの全ての辺は全域木と、グラフの双対の全域木に対応する辺に分解することができる。
このタイプの分解の例は、単純な格子の辺の一部を壁としたようなタイプの迷路で見ることが出きる。このような迷路では壁とその間の空間は互いに入れ子になった木構造を形成する。この木構造は元の格子が形成するグラフの全域木とみなせる。このとき空間が構成する木構造は、元のグラフの双対の全域木となる。
このような2つの木構造への分解は、オイラーの公式の単純な証明を与える。