If I have a graph consisting of 2 disjoint triangles, which are connected by an additional edge, then I have difficulties understanding how its dual graph looks like.
[Math] Dual graph: Simple example
graph theory
Related Solutions
What about such a graph:
$\hspace{50pt}$
You could easily also make it 3-vertex connected, but not 4-vertex connected in the same way, etc.
$\hspace{50pt}$
I hope this helps $\ddot\smile$
TravisJ is correct. The dual graph is defined for graphs in a surface, and depends on both the surface, and exactly how the graph is embedded into it.
For example, consider the "figure 8" graph consisting of a single vertex and two edges connecting it to itself. We can embed this graph in the torus in several ways:
- Limit the embedding to a disk (ignoring the special topology of the torus), as a figure 8. There are 3 faces. The dual consists of 3 vertices connected in a line: $\cdot - \cdot - \cdot$
- One of the edges circles a side of the torus, while the other forms a local loop. Now there are only two faces. The dual consists of 2 vertices, connected by an edge. One of the vertices also has a loop.
- One of the edges circles the torus on its outside, while the other circles around one side of the torus. Now there is only one face. The dual consists of 1 vertex with two loops.
You may be able to prove it more generally than for planar graphs, but the dual of a graph is not a property of the graph itself but rather of its embedding in a surface. So the theorem can only be stated in reference to surfaces.
Addendum I believe the modified question is true: if $G$ is a graph in some surface $S$ such that all the faces of $G$ are simply connected, then the dual of the dual of $G$ is isomorphic to $G$.
To see this, note that because the faces are simply-connected, they are homeomorphic to the unit disk. For each face, choose such a homeomorphism. Under this homeomorphism, the center of the disk is the dual vertex for the face, and the edges of the face are arc segments of the unit circle. The radii connecting the center to the midpoints of the various edges form curves breaking the face into smaller simply connected segments. Combining each of these curves with the corresponding curve in the face on the other side of the edge it leads to forms a dual edge. The dual edges and dual vertices form a representation of $G^*$. However for each vertex of $G$, it is surrounded by a finite number of those smaller simply connected segments, which combine together to form a dual face for the dual graph with the vertex inside it. Further, the portions of the original edges on this side of their midpoints connect the vertex to one point on each of the surrounding dual edges. Thus the original graph $G$ forms a representation of the dual of the graph $G^*$.
This argument (which I've only outlined) follows the same lines as the planar proof. Because of the assumption that the faces are simply connected, the topology of the surface does not get in the way of the proof.
Best Answer
Here is a picture. The dual graph is in green.