10.2Duality24910.1.9 Show that cr(Kn)/(°) is a monotonically increasing function of n10.1.10 A graph G is crossing-minimal if cr(G /e) < cr(G) for all e E E. Showthateverynonplanaredge-transitivegraphiscrossing-minimal10.1.11 A thrackle is a graph embedded in the plane in such a way that any twoedges intersect exactly once (possibly at an end). Such an embedding is called athrackle embedding. Show that:a) every tree has a thrackle embedding.b) the 4-cycle has no thrackle embedding,c) the triangle and every cycle of length five or more has a thrackle embedding.10.1.12 Show that every simple graph can be embedded in R3 in such a way that:a) each vertex lies on the curve (t, t?, t3) : t e R],(C. THOMASSEN)b)each edge isa straight line segment10.2DualityFACESAplanegraph Gpartitions the rest oftheplaneintoanumberofarcwise-connectedopen sets. These sets are called the faces of G. Figure 10.7 shows a plane graphwith five faces, fi, f2, f3, f4, and fs. Each plane graph has exactly one unboundedface,called the outer face.In the planegraph of Figure 10.7.the outer face isfi. We denote by F(G) and f(G), respectively, the set of faces and the numberof faces of aplane graph G.Thenotion of a faceapplies alsoto embeddings ofgraphs on other surfaces.15C4Fig. 10.7. A plane graph with five faces10.2 Duality 249 10.1.9 Show that cr(Kn)/ n 4  is a monotonically increasing function of n. 10.1.10 A graph G is crossing-minimal if cr(G \ e) < cr(G) for all e ∈ E. Show that every nonplanar edge-transitive graph is crossing-minimal. 10.1.11 A thrackle is a graph embedded in the plane in such a way that any two edges intersect exactly once (possibly at an end). Such an embedding is called a thrackle embedding. Show that: a) every tree has a thrackle embedding, b) the 4-cycle has no thrackle embedding, c) the triangle and every cycle of length five or more has a thrackle embedding. ————— ————— 10.1.12 Show that every simple graph can be embedded in R3 in such a way that: a) each vertex lies on the curve {(t,t2,t3) : t ∈ R}, b) each edge is a straight line segment. (C. Thomassen) 10.2 Duality Faces A plane graph G partitions the rest of the plane into a number of arcwise-connected open sets. These sets are called the faces of G. Figure 10.7 shows a plane graph with five faces, f1,f2,f3,f4, and f5. Each plane graph has exactly one unbounded face, called the outer face. In the plane graph of Figure 10.7, the outer face is f1. We denote by F(G) and f(G), respectively, the set of faces and the number of faces of a plane graph G. The notion of a face applies also to embeddings of graphs on other surfaces. v1 v2 v3 v5 v4 v7 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 f1 f2 f3 f4 f5 Fig. 10.7. A plane graph with five faces