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