Let $G$ be a connected graph. An algebraic dual of $G$ is a graph $G'$ such that $G$ and $G'$ have the same set of edges, any cycle of $G$ is a cut of $G'$, and any cut of $G$ is a cycle of $G'$.
Prove the following :
A connected graph $G$ is planar if and only if it has an algebraic dual.
If $M$ is the graphic matroid of a graph $G$, then the dual matroid of $M$ is a graphic matroid if and only if $G$ is planar. If $G$ is planar, the dual matroid is the graphic matroid of the dual graph of $G$.
Posted: Jun 06 '12
Seen: 33 times
Last updated: Jun 06 '12
