10.2Duality255Proof Because e is not a cut edge, the two faces of G incident with e are distinctdenote them by fi and f2. Deleting e fromGresultsinthemalgamation of fiandfintoasingleface (seeFigure10.12).AnyfaceofGthatisadjacenttoor f2 is adjacent in Gle to f; all other faces and adjacencies between them areunaffected by the deletion of e. Correspondingly, in the dual, the two vertices ftand f2 of G* which correspond to the faces fi and f2 of G are now replaced by asingle vertex of (G e)*, which we may denote by f, and all other vertices of G*are vertices of (G/e)*.Furthermore, any vertex of G*that is adjacent to f*orf is adjacent in (Gle)*to f*,and adjacencies between vertices of (Gle)* otherthan u are the same as in G*.The assertion follows from these observations.口(6)(a)Fig. 10.12. (a) G and G*, (b) G\e and G* /e*Dually, we have:Proposition 10.13 Let G be a connected plane graph, and let e be a link of GThen(G/e)*= G*|e*Proof Because G is connected, G** = G (Exercise 10.2.4). Also, because e isnot a loop of G, the edge e* is not a cut edge of G*, so G* Iet is connected. ByProposition 10.12,(G*|e*)* =G**/e**兰G/eThe proposition follows on taking duals.口Wenow apply Propositions10.12and 10.13 to show that nonseparable planeseparable duals. This fact turns out to be very useful.graphs haveTheorem 10.14 The dual of a nonseparable plane graph is nonseparableProof By induction on the number of edges. Let G be a nonseparable planegraph. The theorem is clearly true if G has at most one edge, so we may assume10.2 Duality 255 Proof Because e is not a cut edge, the two faces of G incident with e are distinct; denote them by f1 and f2. Deleting e from G results in the amalgamation of f1 and f2 into a single face f (see Figure 10.12). Any face of G that is adjacent to f1 or f2 is adjacent in G \ e to f; all other faces and adjacencies between them are unaffected by the deletion of e. Correspondingly, in the dual, the two vertices f ∗ 1 and f ∗ 2 of G∗ which correspond to the faces f1 and f2 of G are now replaced by a single vertex of (G \ e)∗, which we may denote by f ∗, and all other vertices of G∗ are vertices of (G \ e)∗. Furthermore, any vertex of G∗ that is adjacent to f ∗ 1 or f ∗ 2 is adjacent in (G \ e)∗ to f ∗, and adjacencies between vertices of (G \ e)∗ other than v are the same as in G∗. The assertion follows from these observations.
(a) (b) f ∗ f ∗ 1 f ∗ 2 e e∗ Fig. 10.12. (a) G and G∗, (b) G \ e and G∗ / e∗ Dually, we have: Proposition 10.13 Let G be a connected plane graph, and let e be a link of G. Then (G/e) ∗ ∼= G∗ \ e∗ Proof Because G is connected, G∗∗ ∼= G (Exercise 10.2.4). Also, because e is not a loop of G, the edge e∗ is not a cut edge of G∗, so G∗ \ e∗ is connected. By Proposition 10.12, (G∗ \ e∗) ∗ ∼= G∗∗ /e∗∗ ∼= G/e The proposition follows on taking duals.
We now apply Propositions 10.12 and 10.13 to show that nonseparable plane graphs have nonseparable duals. This fact turns out to be very useful. Theorem 10.14 The dual of a nonseparable plane graph is nonseparable. Proof By induction on the number of edges. Let G be a nonseparable plane graph. The theorem is clearly true if G has at most one edge, so we may assume