Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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