10.2Duality251Fig.10.8. Subdivision of a face f by an edge alsofacesofG+eand thefaceisreplacedbytwonewfaces,fiand f2whichmeet in the edge e, as illustrated in Figure 10.8.In a connected plane graph the boundary of a face can be regarded as a closedwalk in which each cut edge of the graph that lies in the boundary is traversedtwice. This is clearly so for plane trees, and can be established in general by induction on the number of faces (Exercise 10.2.2.) In the plane graph of Figure 10.7,forinstancea(f3)=Vieivae2uge1ose7ueeeieguiand a(fs)=ieeugeguege7vsegu1Moreover, in the case of nonseparable graphs, these boundary walks are simplycycles, as was shown by Whitney (1932c)Theorem 10.7In a nonseparable plane graph other than Ki or K2,each face isbounded by a cycle.ProoLet G bonseparable plane graph. Consider an ear deccDositioGo.Gr...,Gk of G, where Gg is a cycle, Gk = G, and, for 0<i≤ k -2,Gi+1:=G,UP, is a nonseparable plane subgraph of G, where P, is an ear of GSince Go is a cycle, the two faces of Go are clearly bounded by cycles. Assume.inductively, that all faces of G, are bounded by cycles, where i ≥0. Because Gi+isaplanegraph,theear P,of Gis contained in somefacef of Gi.(MorepreciselyGi+i is obtained from G, by subdividing the face f by an edge joining the endsof P, and then subdividing that edge by inserting the internal vertices of P.)Each face of Giother than f is aface of Gi+t as well,and so, by the inductiohypothesis, is bounded by a cycle. On the other hand, the face f of G, is dividedbyinowofasofGndisasyoseethatthee,ooarebounddy口cyclesOne consequence of Theorem 10.7 is that all planar graphs without cut edgeshave cycle double covers (Exercise 10.2.8). Another is the following.Corollary 10.8 In a loopless 3-connected plane graph, the neighbours of any verter lie on a common cycle.10.2 Duality 251 f f1 f2 e Fig. 10.8. Subdivision of a face f by an edge e also faces of G + e, and the face f is replaced by two new faces, f1 and f2, which meet in the edge e, as illustrated in Figure 10.8. In a connected plane graph the boundary of a face can be regarded as a closed walk in which each cut edge of the graph that lies in the boundary is traversed twice. This is clearly so for plane trees, and can be established in general by induc￾tion on the number of faces (Exercise 10.2.2.) In the plane graph of Figure 10.7, for instance, ∂(f3) = v1e1v2e2v3e10v5e7v6e6v1e9v1 and ∂(f5) = v1e6v6e8v7e8v6e7v5e5v1 Moreover, in the case of nonseparable graphs, these boundary walks are simply cycles, as was shown by Whitney (1932c). Theorem 10.7 In a nonseparable plane graph other than K1 or K2, each face is bounded by a cycle. Proof Let G be a nonseparable plane graph. Consider an ear decomposition G0,G1,...,Gk of G, where G0 is a cycle, Gk = G, and, for 0 ≤ i ≤ k − 2, Gi+1 := Gi ∪ Pi is a nonseparable plane subgraph of G, where Pi is an ear of Gi. Since G0 is a cycle, the two faces of G0 are clearly bounded by cycles. Assume, inductively, that all faces of Gi are bounded by cycles, where i ≥ 0. Because Gi+1 is a plane graph, the ear Pi of Gi is contained in some face f of Gi. (More precisely, Gi+1 is obtained from Gi by subdividing the face f by an edge joining the ends of Pi and then subdividing that edge by inserting the internal vertices of Pi.) Each face of Gi other than f is a face of Gi+1 as well, and so, by the induction hypothesis, is bounded by a cycle. On the other hand, the face f of Gi is divided by Pi into two faces of Gi+1, and it is easy to see that these, too, are bounded by cycles.
One consequence of Theorem 10.7 is that all planar graphs without cut edges have cycle double covers (Exercise 10.2.8). Another is the following. Corollary 10.8 In a loopless 3-connected plane graph, the neighbours of any ver￾tex lie on a common cycle