《图论》课程教学资源（书籍文献）Graph Theory II（10-17，J.A. Bondy，U.S.R. Murty）

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 assume

10.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

25610 Planar GraphsthatGhas atleasttwo edges,hencenoloopsorcut edges.Let e be an edge of GThen either Ge or G /e is nonseparable (Exercise 5.3.2). If Gle is nonseparableso is (G |e)* G* /e*, by the induction hypothesis and Proposition 10.12. ApplyingExercise5.2.2b,we deduce that G*isnonseparable.ThecasewhereG/eisnonseparablecanbeestablished byananalogousargumentLThe dual of any plane graph is connected, and it follows from Theorem 10.14that the dual of a loopless 2-connected plane graph is 2-connected. Furthermore,one can show that the dual of a simple 3-connected plane graph is 3-connected(Exercise 10.2.7)The notion of plane duality can be extended to directed graphs. Let D beplane digraph, with underlying plane graph G. Consider a plane dual G* of G.Each arc a of D separates two faces of G. As a is traversed from its tail to itshead, one of these faces lies to the left of a and one to its right. We denote thesetwo faces by la and ra, respectively; note that if a is a cut edge, la = Ta. Foreach arc a of D,we now orientthe edgeof G*that crosses it as an arc a*bydesignating the end lying in l. as the tail of a* and the end lying in ra as its head.The resulting plane digraph D* is the directed plane dual of D. An example isshown in Figure10.13.Fig.10.13. An orientation of the triangular prism, and its directed plane dualVECTORSPACESANDDUALITYWe have seen that the cycle and bond spaces are orthogonal complements (Exer-cise 2.6.4a). In the case of plane graphs, this relationship of orthogonality can alsobe expressed in terms of duality, as we now explain. As usual in this context, weidentify cycles, trees, and cotrees with their edge setsWe observed earlier that all duals are connected (Proposition 10.9). A similarargument, based on the fact that the interior of a cycle in a plane graph is arcwiseonnected, establishes the following proposition

256 10 Planar Graphs that G has at least two edges, hence no loops or cut edges. Let e be an edge of G. Then either G\ e or G/e is nonseparable (Exercise 5.3.2). If G\ e is nonseparable, so is (G \ e)∗ ∼= G∗ /e∗, by the induction hypothesis and Proposition 10.12. Ap￾plying Exercise 5.2.2b, we deduce that G∗ is nonseparable. The case where G/e is nonseparable can be established by an analogous argument.
The dual of any plane graph is connected, and it follows from Theorem 10.14 that the dual of a loopless 2-connected plane graph is 2-connected. Furthermore, one can show that the dual of a simple 3-connected plane graph is 3-connected (Exercise 10.2.7). The notion of plane duality can be extended to directed graphs. Let D be a plane digraph, with underlying plane graph G. Consider a plane dual G∗ of G. Each arc a of D separates two faces of G. As a is traversed from its tail to its head, one of these faces lies to the left of a and one to its right. We denote these two faces by la and ra, respectively; note that if a is a cut edge, la = ra. For each arc a of D, we now orient the edge of G∗ that crosses it as an arc a∗ by designating the end lying in la as the tail of a∗ and the end lying in ra as its head. The resulting plane digraph D∗ is the directed plane dual of D. An example is shown in Figure 10.13. Fig. 10.13. An orientation of the triangular prism, and its directed plane dual Vector Spaces and Duality We have seen that the cycle and bond spaces are orthogonal complements (Exer￾cise 2.6.4a). In the case of plane graphs, this relationship of orthogonality can also be expressed in terms of duality, as we now explain. As usual in this context, we identify cycles, trees, and cotrees with their edge sets. We observed earlier that all duals are connected (Proposition 10.9). A similar argument, based on the fact that the interior of a cycle in a plane graph is arcwise￾connected, establishes the following proposition

10.2Duality257Proposition 10.15 Let G be a plane graph, G* a plane dual of G, C a cycle ofG, and X* the set of vertices of G* that lie in int(C). Then G*[X*I is connectedFor a subset S of E(G), we denote by S* the subset (et : e e S) of E(G*)Theorem 10.16 Let G be a connected plane graph, and let G* be a plane dual ofa) IfC is a cycle of G, then Ct is a bond of Gt.b) If B is a bond of G, then B* is a cycle of G*.Proof a) Let C bea cycle of G, and let X denote the set of vertices of G* thatlie in int(C).Then C*isthe edge cut a(X)in G*By Proposition10.15, thesubgraph of G* induced by X* is connected. Likewise, the subgraph of G* inducedby V(G*) I X* is connected. It follows from Theorem 2.15 that C* is a bond ofG*. We leave part (b) (the converse of (a) as an exercise (Exercise 10.2.9).口As a straightforward consequence of Theorem 10.16, we have:Corollary 10.17 For any plane graph G, the cycle space of G is isomorphic tothe bond space of G*LThe relationship between cycles and bonds expressed in Theorem 10.16 mayberefinedbytakinientations into account and considering directed duals, asdefined abovve. Let D be a plane digraph and D* its directed plane dual. For asubset S of A(D), denote by S* the subset a* : a E S) of A(D*).Theorem 10.18 Let D be a connected plane digraph and let D* be a plane directeddual of Da) Let C be a cycle of D, with a prescribed sense of traversal. Then C* is a bonda(X*)of D*. Moreover the set of forwardarcs of C cormsponds to the outcut+(X*) and the set of reverse arcs of C to the incut a-(X*)b) Let B := o(X) be a bond of D. Then B* is a cycle of D*, Moreover the outcutO+(X) corresponds to the set of forward arcs of Bt and the incut a-(X)corresponds to the set of reverse arcs of B* (with respect to a certain sense of一traversalofB*).The proof of Theorem 10.18 is left to the reader (Exercise 10.2.13).Exercises10.2.1a) Show that a graph is planar if and only if each of its blocks is planalb) Deduce that every minimal nonplanar graph is both simple and nonseparable

10.2 Duality 257 Proposition 10.15 Let G be a plane graph, G∗ a plane dual of G, C a cycle of G, and X∗ the set of vertices of G∗ that lie in int(C). Then G∗[X∗] is connected.
For a subset S of E(G), we denote by S∗ the subset {e∗ : e ∈ S} of E(G∗). Theorem 10.16 Let G be a connected plane graph, and let G∗ be a plane dual of G. a) If C is a cycle of G, then C∗ is a bond of G∗. b) If B is a bond of G, then B∗ is a cycle of G∗. Proof a) Let C be a cycle of G, and let X∗ denote the set of vertices of G∗ that lie in int(C). Then C∗ is the edge cut ∂(X∗) in G∗. By Proposition 10.15, the subgraph of G∗ induced by X∗ is connected. Likewise, the subgraph of G∗ induced by V (G∗) \ X∗ is connected. It follows from Theorem 2.15 that C∗ is a bond of G∗. We leave part (b) (the converse of (a)) as an exercise (Exercise 10.2.9).
As a straightforward consequence of Theorem 10.16, we have: Corollary 10.17 For any plane graph G, the cycle space of G is isomorphic to the bond space of G∗.
The relationship between cycles and bonds expressed in Theorem 10.16 may be refined by taking orientations into account and considering directed duals, as defined above. Let D be a plane digraph and D∗ its directed plane dual. For a subset S of A(D), denote by S∗ the subset {a∗ : a ∈ S} of A(D∗). Theorem 10.18 Let D be a connected plane digraph and let D∗ be a plane directed dual of D. a) Let C be a cycle of D, with a prescribed sense of traversal. Then C∗ is a bond ∂(X∗)of D∗. Moreover the set of forward arcs of C corresponds to the outcut ∂+(X∗) and the set of reverse arcs of C to the incut ∂−(X∗). b) Let B := ∂(X) be a bond of D. Then B∗ is a cycle of D∗. Moreover the outcut ∂+(X) corresponds to the set of forward arcs of B∗ and the incut ∂−(X) corresponds to the set of reverse arcs of B∗ (with respect to a certain sense of traversal of B∗).
The proof of Theorem 10.18 is left to the reader (Exercise 10.2.13). Exercises 10.2.1 a) Show that a graph is planar if and only if each of its blocks is planar. b) Deduce that every minimal nonplanar graph is both simple and nonseparable

25810 Planar Graphs+10.2.2 Prove that the boundary of a face of a connected plane graph can beregarded asaclosed walkin whicheach cut edgeofthegraphlying intheboundaryis traversed twice.10.2.3 Determine the duals of the five platonic graphs (Figure 1.14).10.2.4 Let G be a plane graph. Show that Q** G if and only if G is connected.+10.2.5 Show that every simple connected plane graph on n vertices, where n ≥ 3,is a spanning subgraph of a triangulation10.2.6 Let G be a triangulationn on at least four vertices. Show that G* is a simplnonseparable cubic plane graph.10.2.7Show that the dualofasimple 3-connected plane graphisbothsimple andconnected10.2.8 Show that every planar graph without cut edges has a cycle double cover+10.2.9 ShoW that if B is a bond of a plane graph G, then B* is a cycle of itsplane dual G*10.2.10a) Show that the dual of an even plane graph is bipartite (and conversely)b)AHamilbond of a connected graphG is a bond B such that both compoments of GB are trees. Let G be a plane graph which contaIsaHamiltorcycle,and let Cbe (theedge set of)suchacycle. Show that C*isa Hamiltonbond of G*10.2.11 OUTERPLANAR GRAPHAgraph G is outerplanarifit has a planar embedding G in which all vertices lieon the beboundary of its outer face. An outerplanar graph equipped with such anembedding is called an outerplane graph. Show that:a) if G is an outerplane graph, then the subgraph of G* induced by the verticescorrespondingtotheinteriorfacesofGisatreeb) every simple 2-connected outerplanar graph other than K2 has a vertex ofdegree two.10.2.12 Let T bepanningtreeofanected plane graph G. Show that (E\T)*Sis a spanning tree of G**10.2.13 Prove Theorem 10.18.10.2.14 A Halin graph is a graph H :=TUC, where T is a plane tree on at leastfour vertices in which no vertex has degree two, and Cis a cycle connecting theleaves of T in the cyclic order determined by the embedding of T. Show that:

258 10 Planar Graphs 10.2.2 Prove that the boundary of a face of a connected plane graph can be regarded as a closed walk in which each cut edge of the graph lying in the boundary is traversed twice. 10.2.3 Determine the duals of the five platonic graphs (Figure 1.14). 10.2.4 Let G be a plane graph. Show that G∗∗ ∼= G if and only if G is connected. 10.2.5 Show that every simple connected plane graph on n vertices, where n ≥ 3, is a spanning subgraph of a triangulation. 10.2.6 Let G be a triangulation on at least four vertices. Show that G∗ is a simple nonseparable cubic plane graph. 10.2.7 Show that the dual of a simple 3-connected plane graph is both simple and 3-connected. 10.2.8 Show that every planar graph without cut edges has a cycle double cover. 10.2.9 Show that if B is a bond of a plane graph G, then B∗ is a cycle of its plane dual G∗. 10.2.10 a) Show that the dual of an even plane graph is bipartite (and conversely). b) A Hamilton bond of a connected graph G is a bond B such that both compo￾nents of G \ B are trees. Let G be a plane graph which contains a Hamilton cycle, and let C be (the edge set of) such a cycle. Show that C∗ is a Hamilton bond of G∗. 10.2.11 Outerplanar Graph A graph G is outerplanar if it has a planar embedding G in which all vertices lie on the boundary of its outer face. An outerplanar graph equipped with such an embedding is called an outerplane graph. Show that: a) if G is an outerplane graph, then the subgraph of G∗ induced by the vertices corresponding to the interior faces of G is a tree, b) every simple 2-connected outerplanar graph other than K2 has a vertex of degree two. 10.2.12 Let T be a spanning tree of a connected plane graph G. Show that (E\T)∗ is a spanning tree of G∗. 10.2.13 Prove Theorem 10.18. ————— ————— 10.2.14 A Halin graph is a graph H := T ∪ C, where T is a plane tree on at least four vertices in which no vertex has degree two, and C is a cycle connecting the leaves of T in the cyclic order determined by the embedding of T. Show that:

10.3 Euler's Formula259a) every Halin graph is minimally 3-connected,b) every Halin graph has a Hamilton cycle.10.2.15 The medial graph of a plane graph G is the 4-regular graph M(G) withvertex set E(G) in which two vertices are joined by k edges if, in G, they arelon faces (k = 0, 1,2). (The medialadjacent edges which are incident to k ccgraph has a natural planar embedding.) Let G be a nonseparable plane graph.Showthat:a) M(G) is a 4-regular planar graph,b) M(G) = M(G*).10.3 Euler's FormulaThere is a simple formula relating the numbers of vertices, edges, and faces ina connected plane graph. It was first established for polyhedral graphs by Euler(1752), and is known as Euler's Formala.Theorem 10.19EULER'S FORMULAFor a connected plane graph G,(10.2)v(G) - e(G) + f(G) = 2Proof By induction on f(G), the ntroffacces of G. If f(G) = 1, each edge ofG is a cut edge and so G, being connected, is a tree. In this case e(G) = v(G)-1,by Theorem 4.3, and the assertion holds. Suppose that it is true for all connectedplane graphs with fewer than f faces, where f ≥ 2, and let G be a connected planegraph with f faces. Choose an edge e of G that is not a cut edge. Then G)e is aconnected plane graph with f -1 faces, because the two faces of G separated bye.coalesce to form one face of G/e.By the induction hypothesis.v(G le) -e(Gle) + f(Gle) = 2Using the relationsv(G /e) = v(G),(e(G/e)=e(G) -1, and f(G e)= f(G)-1we obtainv(G) - e(G) + f(G) = 2口The theorem follows by induction.Corollary10.20 All planarembeddings ofa connected planar graph have the samenumber of faces

10.3 Euler’s Formula 259 a) every Halin graph is minimally 3-connected, b) every Halin graph has a Hamilton cycle. 10.2.15 The medial graph of a plane graph G is the 4-regular graph M(G) with vertex set E(G) in which two vertices are joined by k edges if, in G, they are adjacent edges which are incident to k common faces (k = 0, 1, 2). (The medial graph has a natural planar embedding.) Let G be a nonseparable plane graph. Show that: a) M(G) is a 4-regular planar graph, b) M(G) ∼= M(G∗). 10.3 Euler’s Formula There is a simple formula relating the numbers of vertices, edges, and faces in a connected plane graph. It was first established for polyhedral graphs by Euler (1752), and is known as Euler’s Formula. Theorem 10.19 Euler’s Formula For a connected plane graph G, v(G) − e(G) + f(G) = 2 (10.2) Proof By induction on f(G), the number of faces of G. If f(G) = 1, each edge of G is a cut edge and so G, being connected, is a tree. In this case e(G) = v(G) − 1, by Theorem 4.3, and the assertion holds. Suppose that it is true for all connected plane graphs with fewer than f faces, where f ≥ 2, and let G be a connected plane graph with f faces. Choose an edge e of G that is not a cut edge. Then G \ e is a connected plane graph with f − 1 faces, because the two faces of G separated by e coalesce to form one face of G \ e. By the induction hypothesis, v(G \ e) − e(G \ e) + f(G \ e)=2 Using the relations v(G \ e) = v(G), e(G \ e) = e(G) − 1, and f(G \ e) = f(G) − 1 we obtain v(G) − e(G) + f(G)=2 The theorem follows by induction.
Corollary 10.20 All planar embeddings of a connected planar graph have the same number of faces