In: Advanced Math
The construction of a dual D(G) can be applied in any plane graph G: draw a vertex of D(G) in the middle of each region of G and draw an edge e* of D(G) perpendicular to each edge e of G; e* connects the vertices of D(G) representing the regions on either side of e.
a) A dual need not be a graph. It might have two edges between the same pair of vertices or a self-loop edge (from a vertex to itself). find two planar graphs with duals that are not graphs because they contain these two forbidden situations.
C) Show that the degree of a vertex in dual graph D(G) equals the number of boundary edges of the corresponding region in the planar graph G.
E) show for any plane depiction of a graph G that the vertices of G correspond to regions in D(G)
a)
C) In the example we have drawn
degree (w1)= 3, the region (whose middle point is w1 has three boundary edges {v1, v4}, {v1, v2}, {v2, v4},
degree (w2)= 3, the region (whose middle point is w2 has three boundary edges {v2, v4}, {v3, v2}, {v3, v4},
degree (w3)= 4, the region (whose middle point is w3 has four boundary edges {v1, v4}, {v1, v2}, {v2, v3}, {v3, v4},
Observe that degree of each vertex of D(G) and the region bounded by the edges of the region are equal.
E) In the dual graph D(G) has four regions, and the first region has v1 in the interior, the second region has v2 in the interior, the third region has v3 in the interior, and the fourth region has v4 in the interior. Thus the vertices of G correspond to regions in D(G)