Suggest a Book

# Algebraic dual of graphs

Level: unknown

posted Jun 06 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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$.

delete retag edit

## Stats

Posted: Jun 06 '12

Seen: 33 times

Last updated: Jun 06 '12