📂Graph Theory

Abstract Dual Graphs

Buildup

Properties of Geometric Dual Graphs [3]: For a planar graph $G$ and its geometric dual graph $G^{ \ast }$, if $C \subset E(G)$ is a cycle then $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$ is a cutset

Abstract Dual Graphs are defined abstractly for general graphs unlike geometric dual graphs which are intuitive for planar graphs. A graph is called a dual graph if it possesses the properties of a dual, not by how it is constructed.

Definition ¹

Given a graph $G$, $G^{ \ast }$ is called the abstract dual graph of $G$ if there exists a one-to-one correspondence between $E(G)$ and $E \left( G^{ \ast } \right)$ that satisfies the following.

Basic Properties

Abstract dual graphs have the following common-sense properties.

• [1]: If $G^{ \ast }$ is the abstract dual of $G$, then $G$ is the abstract dual of $G^{ \ast }$.
• [2]: A graph being planar is equivalent to it having an abstract dual.

Explanation

Property [2] uses Kuratowski’s theorem in its proof, which doesn’t make the argument any stronger, so it might not be worth proving by the learner. However, the statement’s conveyed meaning is still notable. The existence of an abstract dual for a planar graph is expected, but the fact that any form of dual implies the original graph’s structure is not mathematically trivial.

This concept of duality leads to matroids in combinatorial theory.