1
$\begingroup$

Let $G$ be a graph. The abstract dual of $G$ can be defined as a graph $G^*$ whose edges are in one to one correspondence with $G$ and whose spanning trees are obtained by taking the complements of the images of the spanning trees of $G$. Using this definition and Whitney's theorem (A graph is planar iff it has an abstract dual) I wish to establish that $K_{3,3}$ is non planar.

But I find another definition of dual on wikipedia according to which cycles are sent to cuts and cuts to cycles. This definition has also been implicitly used in the above linked proof for non planarity of $K_5$. So I am confused now. Given the abstract dual $G^*$ is it true that cycles of $G$ correspond to cuts of $G^*$ and cuts of $G$ to cycles of $G^*$?

$\endgroup$
1
$\begingroup$

There are two different duels of graphs. Don't confuse the two. One is the Geometric Dual and the other is the Abstract Dual.

The Abstract Dual does hold true saying that graph G is planar if and only if there is an Abstract Dual.

A Geometric Dual has the property that a subset of the edges of G form a cycle in G if and only if the corresponding subset of the edges of G* is a cutset of G*.

There are two different drawings for duels since the Abstract Dual has a one-to-one correspondence between the edges, which does not necessarily hold true for Geometric Duals.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.