2
$\begingroup$

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?

  • 0
    @utdiscant Of course.2012-06-08

2 Answers 2

2

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

  • 0
    Nice answer! You can easily imagine putting this graph on, say, a sphere and ending up with a non-simple dual graph.2012-06-05
1

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.

  • 0
    My answer is true for the sphere though.2012-06-07