(a) Show that the graphs in Fig. 11.73 are isomorphic.
(b) Draw a dual for each graph.
(c) Show that the duals obtained in part (b) are not isomorphic.
(d) Two graphs G and H are called 2-isomorphic if one can be obtained from the other by applying either or both of the following procedures a finite number of times.

(1) In Fig. 11.74 we split a vertex, namely r, of G and obtain the graph H, which is disconnected.
(2) In Fig. 11.75 we obtain graph (d) from graph (a) by
(i) first splitting the two distinct vertices j and q - disconnecting the graph,
(ii) then reflecting one subgraph about the horizontal axis, and
(iii) then identifying vertex j(q) in one subgraph with vertex q(j) in the other subgraph.
Prove that the dual graphs obtained in part (c) are 2- isomorphic.

(e) For the cut-set {{a, b}, {c, b}, {d, b}} in part (a) of Fig. 11.73, find the corresponding cycle in its dual. In the dual of the graph in Fig. 11.73(b), find the cut-set that corresponds with the cycle {w, z}, {z, x}, {x, y}, {y, w] in the given graph.

Transcribed Image Text:

Figure 11.73 Figure 11.74