Lagmental Vicfred

Planar Duality Exchanges Cycles and Cuts by Vicfred

Last updated: Wed 28 August 2024

tags: mathematics, planar graphs, coloring, duality

Edges crossing a primal cut form a cycle in the geometric dual and vice versa. The formulas are more useful when each symbol has a job rather than merely decorating the theorem.

Statement

A planar embedding divides the sphere into vertices, edges, and faces. Euler's relation \(|V|-|E|+|F|=2\) constrains density, while the dual \(G^\ast\) records adjacency of faces.

$$ G^\ast=(F(G),E^\ast) $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ (G^\ast)^\ast\cong G\quad\text{for a connected plane graph} $$

Worked algebra

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ e\ \text{bridge in }G\Longleftrightarrow e^\ast\ \text{loop in }G^\ast,\qquad T\text{ spanning tree}\Longleftrightarrow E^\ast\setminus T^\ast\text{ spanning tree of }G^\ast $$

Conceptual compression

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad G^\ast=(F(G),E^\ast),\\[5pt] \mathsf{C}\;&:\quad (G^\ast)^\ast\cong G\quad\text{for a connected plane graph}. \end{aligned} $$

Caveat

Planarity is a property of a graph, while a plane graph includes a chosen embedding. The dual depends on that embedding.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] (G^\ast)^\ast\cong G\quad\text{for a connected plane graph} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Tue 28 February 2023. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.