24810 Planar Graphs+10.1.3a) Show that the Petersen graph contains a subdivision of K3.3b) Deduce that the Petersen graph is nonplanar.+10.1.4Let G be a planar graph, and let e be a link of G. Show that G /e is planar.b)Is the converse true?+10.1.5 Let G be a simple nontrivial graph in which each vertex, except possibly one, has degree at least three. Show, by induction on n, that G contains asubdivision of K4.10.1.6 Find a planar embedding of the graph in Figure 10.6 in which each edge isstraight linesegment(Wagner (1936) proved that every simple planar graph admits such an embedding.)Fig. 10.6. Finddingof thisgraph(Exercise10.1.6)10.1.7 Ak-book isa topological subspace of R3 consisting of k unit squaralleits pages, that have one side in common, called its spine, but are pairwise disjointotherwise. Show that any graph G is embeddable in R3 by showing that it isembeddable in a k-book, for some k.10.1.8 Consider a drawing G of a (not necessarily planar) graph G in the planeTwo edges of G crossif they meet at a point other than a vertex of G.Each suchpoint is called a crossing of the two edges. The crossing number of G, denoted bycr(G), is the least number of crossings in a drawing of G in the plane. Show that:a) cr(G) = 0 if and only if G is planar.b)cr(Ks)=cr(K33)=1c) cr(Pio) = 2, where Pio is the Petersen graph,d) cr(K6) = 3.248 10 Planar Graphs 10.1.3 a) Show that the Petersen graph contains a subdivision of K3,3. b) Deduce that the Petersen graph is nonplanar. 10.1.4 a) Let G be a planar graph, and let e be a link of G. Show that G/e is planar. b) Is the converse true? 10.1.5 Let G be a simple nontrivial graph in which each vertex, except possi￾bly one, has degree at least three. Show, by induction on n, that G contains a subdivision of K4. 10.1.6 Find a planar embedding of the graph in Figure 10.6 in which each edge is a straight line segment. (Wagner (1936) proved that every simple planar graph admits such an embedding.) Fig. 10.6. Find a straight-line planar embedding of this graph (Exercise 10.1.6) 10.1.7 A k-book is a topological subspace of R3 consisting of k unit squares, called its pages, that have one side in common, called its spine, but are pairwise disjoint otherwise. Show that any graph G is embeddable in R3 by showing that it is embeddable in a k-book, for some k. 10.1.8 Consider a drawing G of a (not necessarily planar) graph G in the plane. Two edges of G cross if they meet at a point other than a vertex of G. Each such point is called a crossing of the two edges. The crossing number of G, denoted by cr(G), is the least number of crossings in a drawing of G in the plane. Show that: a) cr(G) = 0 if and only if G is planar, b) cr(K5) = cr(K3,3) = 1, c) cr(P10) = 2, where P10 is the Petersen graph, d) cr(K6) = 3