# Is the dual graph simple?

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every edge the corresponding faces have in common in the original graph.

My question is this: Let $G$ be cellularly embedded in some surface and let $G'$ be the dual of this embedding. If $\delta (G)\geq 3$, can I be sure that $G'$ is simple (there is at most one edge between two vertices)?

This should be simple, but I am not comfortable enough with proofs in topological graph theory.

Note: $\delta (G)$ denotes the minimum degree of vertices in $G$.

Edit: Follow-up to this question: When is the dual graph simple?

-
Could you provide a definition of $\delta(G)$? – MartianInvader Jun 5 '12 at 19:47
@MartianInvader Sure. Edited the question. – becko Jun 5 '12 at 19:54
@becko If you are satisfied with any of the answers, remember to mark it as correct. – utdiscant Jun 7 '12 at 11:37
@utdiscant Of course. – becko Jun 8 '12 at 3:21

I am not strong in topological graph theory, but I am pretty sure this should hold on all surfaces.

Create a graph $G$ in the following way. Create two diamonds (graph on 4 vertices, where two triangles are sharing an edge). Now create an edge joining a vertex of degree 2 in one diamond to a vertex of degree 2 in the other diamond. At last join the two remaining vertices of degree 2.

Now the dual graph $G'$ has 6 vertices, where two of them $v,u$ corresponds to faces of degree 6 in $G$. There is 2 edges from $u$ to $v$, thus $G'$ is a multigraph.

This graph is shown as the second to last graph here: http://mathworld.wolfram.com/CubicGraph.html

-
Nice answer! You can easily imagine putting this graph on, say, a sphere and ending up with a non-simple dual graph. – MartianInvader Jun 5 '12 at 22:56

If the graph has an edge cut of size 1, then dual will have a loop. If it has an edge cut of size 2, then the dual will have a multiple edge.So, the dual will be simple if the edge connectivity of the graph is greater or equal to 3.

-
This is not true on any surface. Consider the circular ladder graph embedded around a torus. The circular ladder graph is 3-edge connected, but has a multigraph as its dual graph. – utdiscant Jun 6 '12 at 5:48
My answer is true for the sphere though. – hbm Jun 7 '12 at 5:05