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: