10.2Duality253Fig.10.10.The plane graph of Figure10.7and its plane dualProposition 10.9 The dual of any plane graph is connected.Proof Let G be a plane graph and G* a plane dual of G. Consider any two verticesof G*.Thereis a curvein the plane connecting thennwhichavoidsall verticesofG. The sequence of faces and edges of G traversed by this curve corresponds in G*to a walk connecting the two vertices.口Although defined abstractly.it is often convenient to regard the dual G* of plane graph G as being itself a plane graph, embedded as described above. Onemaythen consider thedual**ofWhen Gisconnected, itisnot dificulttoprove that G** = G (Exercise 10.2.4); a glance at Figure 10.10 indicates why thisSSIt should be noted that isomorphic plane graphs may well have nonisomorphicduals. For example, although the plane graphs in Figure 10.1l are isomorphic, theirduals arenot:the:ohshowninFigure10.1lahastwofacesofdegreethDlanegrarwhereas that of Figure i0.ilb has only one such face. Thus the notion of a dualgraph is meaningful only for plane graphs, and not for planar graphs in generalWe show, however (in Theorem 10.28) that every simple 3-connected planar graphhas a unique planar embedding (in the sense that its face boundaries are uniquelydetermined) and hence has a unique dual.The following relations are direct consequences of the definition of the dual G*u(G*)=f(G), e(G*) = e(G), and dg-(f*)= dc(f) for all f e F(G) (10.1)The next theorem may be regarded as a dual version of Theorem 1.1.Theorem 10.10 If G is a plane graph,Z d(f) = 2mfEF10.2 Duality 253 Fig. 10.10. The plane graph of Figure 10.7 and its plane dual Proposition 10.9 The dual of any plane graph is connected. Proof Let G be a plane graph and G∗ a plane dual of G. Consider any two vertices of G∗. There is a curve in the plane connecting them which avoids all vertices of G. The sequence of faces and edges of G traversed by this curve corresponds in G∗ to a walk connecting the two vertices.
Although defined abstractly, it is often convenient to regard the dual G∗ of a plane graph G as being itself a plane graph, embedded as described above. One may then consider the dual G∗∗ of G∗. When G is connected, it is not difficult to prove that G∗∗ ∼= G (Exercise 10.2.4); a glance at Figure 10.10 indicates why this is so. It should be noted that isomorphic plane graphs may well have nonisomorphic duals. For example, although the plane graphs in Figure 10.11 are isomorphic, their duals are not: the plane graph shown in Figure 10.11a has two faces of degree three, whereas that of Figure 10.11b has only one such face. Thus the notion of a dual graph is meaningful only for plane graphs, and not for planar graphs in general. We show, however (in Theorem 10.28) that every simple 3-connected planar graph has a unique planar embedding (in the sense that its face boundaries are uniquely determined) and hence has a unique dual. The following relations are direct consequences of the definition of the dual G∗. v(G∗) = f(G), e(G∗) = e(G), and dG∗ (f ∗) = dG(f) for all f ∈ F(G) (10.1) The next theorem may be regarded as a dual version of Theorem 1.1. Theorem 10.10 If G is a plane graph, f∈F d(f)=2m