J.A. BondyU.S.R. MurtyGraph Theory (II) Springer
J.A. Bondy U.S.R. Murty Graph Theory ABC Graph Theory (II)
ContentsGraiSubor10pa8StableLhe15ColouringsofMar16Matchi17 Edge Colouring5
Contents 1 Graphs ........................................................ 1 2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Connected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 Nonseparable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Tree-Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 9 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 11 The Four-Colour Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 12 Stable Sets and Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 13 The Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 14 Vertex Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 15 Colourings of Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 16 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 17 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
XIIContents18Han03nsolRefelGeneral N623GraphrDeOthNatIndex637
XII Contents 18 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 19 Coverings and Packings in Directed Graphs . . . . . . . . . . . . . . . . . . . 503 20 Electrical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 21 Integer Flows and Coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 Unsolved Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 General Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Graph Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 Operations and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 Families of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
10Planar GraphsContents10.1 Plane and Planar Graph郑国界务时药桥网务西界湖有有时标技药务会HEORDANRUEHEORESUBDIVISIONS10.2 Duality .ACESDUADELETION-CCNDUALPVECTORSPACESANDDUALITY10.3 Euler's Formula10.4BridgeUOUE10.5 KMINORSWAGNER'S THEOREIZECNIZINGPLANARG10.68NTHEORIENTABLEEMBEDDINGCONJECTURE必究10.7RelatedReadingGRAPHMINORSLIN+:BRAMBLEAMATROIDMINOR10.1 Plane and Planar GraphsA graph is said to be embeddable in the plane, or planar, if it can be drawn inthe plane so that its edges intersect only at their ends. Such a drawing is called
10 Planar Graphs Contents 10.1 Plane and Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 243 The Jordan Curve Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 244 Subdivisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 10.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Faces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Duals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Deletion–Contraction Duality . . . . . . . . . . . . . . . . . . . . . . 254 Vector Spaces and Duality . . . . . . . . . . . . . . . . . . . . . . . . . . 256 10.3 Euler’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 10.4 Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 Bridges of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Unique Plane Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 10.5 Kuratowski’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Wagner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 Recognizing Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 271 10.6 Surface Embeddings of Graphs . . . . . . . . . . . . . . . . . . . . 275 Orientable and Nonorientable Surfaces . . . . . . . . . . . . . 276 The Euler Characteristic . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 The Orientable Embedding Conjecture . . . . . . . . . . . . . . 280 10.7 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Graph Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Linkages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Brambles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Matroids and Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Matroid Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 10.1 Plane and Planar Graphs A graph is said to be embeddable in the plane, or planar, if it can be drawn in the plane so that its edges intersect only at their ends. Such a drawing is called
24410 Planar Graphsa planar embedding of the graph. A planar embedding G of aaplrgraphGcanbe regarded as a graph isomorphic to G; the vertex set of G is the set of pointsrepresenting the vertices of G, the edge set of G is the set of lines representing theedges of G, and a vertex of G is incident with all the edges of G that contain it.For this reasowe often refertoaplanar embedding Gof aplanargraphGasaplane graph, and we refer to its points as vertices and its lines as edges. Howeverwhen disc both a planar graph G and a plane embedding G of G, in orderto distinguish the two graphs, we call the vertices of G points and its edges linesthus, by the point of Gwe mean the point of Gthat represents the vertex ofG, and by the line e of G we mean the line of G that represents the edge e ofG. Figure 10.1b depicts a planar embedding of the planar graph K, Ie, shown inFigure 10.la.(6)(a)Fig. 10.1. (a) The planar graph Ks /e, and (b) a planar embedding of Ks /eTHE JORDAN CURVE THEOREMIt is evident from the above definition that the study of planar graphnecessarilyinvolves the topology of the plane. We do not attempt here to be strictly rigorous intopological matters, however, and are content to adopt a naive point of view towardthem. This is done so as not to obscure the combinatorial aspects of the theorywhich is our main interest. An elegant and rigorous treatment of the topologicalaspectscanbefoundinthebookbyMoharandThomassen(2001)The results of topology that are especially relevant in the study of planar graphsare those which deal with simple curves. By a curve, we mean a continuous imageof aclosed unitlient.Analogously,closed curveisacontlousimageofa circle. A curve or closed curve is simple if it does not intersect itself (in otherwords, if the mapping is oneto-one).Properties of such curves come into play inthestudyofplanargraphsbecausecvclesinplanegraphsaresimpleclosedcurvesA subset of the plane is arcwise-connected if any two of its points can beconnected by a curve lying entirely within the subset. The basic result of topologythat we need is the Jordan Curve Theorem
244 10 Planar Graphs a planar embedding of the graph. A planar embedding G of a planar graph G can be regarded as a graph isomorphic to G; the vertex set of G is the set of points representing the vertices of G, the edge set of G is the set of lines representing the edges of G, and a vertex of G is incident with all the edges of G that contain it. For this reason, we often refer to a planar embedding G of a planar graph G as a plane graph, and we refer to its points as vertices and its lines as edges. However, when discussing both a planar graph G and a plane embedding G of G, in order to distinguish the two graphs, we call the vertices of G points and its edges lines; thus, by the point v of G we mean the point of G that represents the vertex v of G, and by the line e of G we mean the line of G that represents the edge e of G. Figure 10.1b depicts a planar embedding of the planar graph K5 \ e, shown in Figure 10.1a. (a) (b) Fig. 10.1. (a) The planar graph K5 \ e, and (b) a planar embedding of K5 \ e The Jordan Curve Theorem It is evident from the above definition that the study of planar graphs necessarily involves the topology of the plane. We do not attempt here to be strictly rigorous in topological matters, however, and are content to adopt a naive point of view toward them. This is done so as not to obscure the combinatorial aspects of the theory, which is our main interest. An elegant and rigorous treatment of the topological aspects can be found in the book by Mohar and Thomassen (2001). The results of topology that are especially relevant in the study of planar graphs are those which deal with simple curves. By a curve, we mean a continuous image of a closed unit line segment. Analogously, a closed curve is a continuous image of a circle. A curve or closed curve is simple if it does not intersect itself (in other words, if the mapping is one-to-one). Properties of such curves come into play in the study of planar graphs because cycles in plane graphs are simple closed curves. A subset of the plane is arcwise-connected if any two of its points can be connected by a curve lying entirely within the subset. The basic result of topology that we need is the Jordan Curve Theorem
10.1 Plane and Planar Graphs245Theorem 10.1 THE JORDAN CURVE THEOREMAny simple closed curve C in the plane partitions the rest of the plane into tudisjoint arcwise-connected open sets.Although this theorem is intuitively obvious, giving a formal proof of it is quitetricky.Thetwo open sets into which ae closed curve Cpartitions theplanor and the erterior of C. We denote them by int(C) and ext(C),arecalled the interand their closures by Int(C) and Ext(C), respectively (thus Int(C) n Ext(C) = C)The Jordan Curve Theorem implies that every arc joining a point of int(C) to apoint of ext(C) meets C in at least one point (see Figure 10.2)teext(C)Fig.10.2.The Jordan Curve TheoremFigurebshowsthat thegraph Keisplanar.ThegraphKs,ontheothehand, is not planar. Let us see how the Jordan Curve Theorem can be used todemonstrate this fact.Theorem 10.2 K, is nonplanar.Proof By contradiction. Let G be a planar embedding of Ks, with verticesA.Us.BecauseGiscomplete.anytwo ofitsverticeare joined by an..edge.Nowthecycle=uaisasimplecosed curveitheplane,andthevertex u4 must lie either in int(C) or in ext(C). Without loss of generality, we maysuppose that u4 E int(C). Then the edges vi4, v2u4, v3v4 all lie entirely in int(C),too (apart from their ends V1, V2, v3) (see Figure 10.3).Consider the cycles Ci = v2v3va2,C2:Vi4U3, and C3=iu2U4ui.Observe that v; e ext(C), i = 1,2,3. Because v,us e E(G) and G is a planegraph, it follows fromthe Jordan Curve Theorem that us E ext(C), i = 1,2,3,too. Thus us E ext(C). But now the edge uaus crosses C, again by the JordanCurve Theorem. This contradicts the planarity of the embedding G.口A similar argument can be used toestablish that K3,s is nonplanar, too (Exercise 10.1.1b)
10.1 Plane and Planar Graphs 245 Theorem 10.1 The Jordan Curve Theorem Any simple closed curve C in the plane partitions the rest of the plane into two disjoint arcwise-connected open sets. Although this theorem is intuitively obvious, giving a formal proof of it is quite tricky. The two open sets into which a simple closed curve C partitions the plane are called the interior and the exterior of C. We denote them by int(C) and ext(C), and their closures by Int(C) and Ext(C), respectively (thus Int(C) ∩ Ext(C) = C). The Jordan Curve Theorem implies that every arc joining a point of int(C) to a point of ext(C) meets C in at least one point (see Figure 10.2). C int(C) ext(C) Fig. 10.2. The Jordan Curve Theorem Figure 10.1b shows that the graph K5 \e is planar. The graph K5, on the other hand, is not planar. Let us see how the Jordan Curve Theorem can be used to demonstrate this fact. Theorem 10.2 K5 is nonplanar. Proof By contradiction. Let G be a planar embedding of K5, with vertices v1,v2,v3,v4,v5. Because G is complete, any two of its vertices are joined by an edge. Now the cycle C := v1v2v3v1 is a simple closed curve in the plane, and the vertex v4 must lie either in int(C) or in ext(C). Without loss of generality, we may suppose that v4 ∈ int(C). Then the edges v1v4,v2v4,v3v4 all lie entirely in int(C), too (apart from their ends v1,v2,v3) (see Figure 10.3). Consider the cycles C1 := v2v3v4v2, C2 := v3v1v4v3, and C3 := v1v2v4v1. Observe that vi ∈ ext(Ci), i = 1, 2, 3. Because viv5 ∈ E(G) and G is a plane graph, it follows from the Jordan Curve Theorem that v5 ∈ ext(Ci), i = 1, 2, 3, too. Thus v5 ∈ ext(C). But now the edge v4v5 crosses C, again by the Jordan Curve Theorem. This contradicts the planarity of the embedding G. A similar argument can be used to establish that K3,3 is nonplanar, too (Exercise 10.1.1b)
24610 Planar Graphst(C2nt(C3)nt(C)ext(C)Fig. 10.3. Proof of the nonplanarity of KsSUBDIVISIONSAny graph derived from a graph G by a sequence of edge subdivisions is calleda subdivision of G or a G-subdivision. Subdivisions of Kg and K3.3 are shown inFigure 10.4.XX(a)(b)Fig. 10.4. (a) A subdivision of Ks, (b) a subdivision of K3.3The proof of the following proposition is straightforward (Exercise 10.1.2)Proposition 10.3 A graph G is planar if and only if every subdivision of G isplanar.口BecauseKsandK3.3arenonplanar,Proposition10.3impliesthatnoplanargraph can contain a subdivision of either Ks or K3.3.A fundamental theorem dueto Kuratowski (1930) states that, conversely, every nonplanar graph necessarilycontains a copy of a subdivision of one of these two graphs. A proof of Kuratowski'sTheorem is given in Section 10.5.As mentioned in Chapter 1 and illustrated in Chapter 3, one may considerembeddings of graphs on surfaces other than the plane. We show in Section 10.6
246 10 Planar Graphs v1 v2 v3 v4 C int(C1) ext(C) int(C2) int(C3) Fig. 10.3. Proof of the nonplanarity of K5 Subdivisions Any graph derived from a graph G by a sequence of edge subdivisions is called a subdivision of G or a G-subdivision. Subdivisions of K5 and K3,3 are shown in Figure 10.4. (a) (b) Fig. 10.4. (a) A subdivision of K5, (b) a subdivision of K3,3 The proof of the following proposition is straightforward (Exercise 10.1.2). Proposition 10.3 A graph G is planar if and only if every subdivision of G is planar. Because K5 and K3,3 are nonplanar, Proposition 10.3 implies that no planar graph can contain a subdivision of either K5 or K3,3. A fundamental theorem due to Kuratowski (1930) states that, conversely, every nonplanar graph necessarily contains a copy of a subdivision of one of these two graphs. A proof of Kuratowski’s Theorem is given in Section 10.5. As mentioned in Chapter 1 and illustrated in Chapter 3, one may consider embeddings of graphs on surfaces other than the plane. We show in Section 10.6
10.1Plane and Planar Graphs247that, for every surface S, there exist graphs which are not embeddable on s.Every graphcan, however, be embedded in the 3-dimensional euclidean space R(Exercise 10.1.7).Planar graphs and graphs embeddable on the sphere are one and the same. Tosee this, we make use of a mapping known as stereographic projection. Considera sphere S resting on a plane P, and denote by z the point that is diametricallyopposite the point of contact of S and P.The mapping : SI(z] - P,defined byr(s) = p if and only if the points z, s, and p are collinear, is called a stereographicprojection from z; it is illustrated in Figure 10.5.Fig.10.5. Stereographic projectionTheorem 10.4 A graph G is embeddable on the plane if and only if it is embed-dableonthesphereProof Suppose that G has an embedding G on the sphere. Choose a point z ofthe sphere not in G. Then the image of G under stereographic projection from zis an embedding of G on the plane, The converse is proved similarly.口On many occasions, it is advantageous to consider embeddings of planar graphson the sphere; one instance is provided by the proof of Proposition 10.5 in the nextsection.Exercises+10.1.1 Show that:a) every proper subgraph of K3.3 is planar.b)K3.3isnonplanar10.1.2 Show that a graph is planar if and only if every subdivision of the graphis planar
10.1 Plane and Planar Graphs 247 that, for every surface S, there exist graphs which are not embeddable on S. Every graph can, however, be embedded in the 3-dimensional euclidean space R3 (Exercise 10.1.7). Planar graphs and graphs embeddable on the sphere are one and the same. To see this, we make use of a mapping known as stereographic projection. Consider a sphere S resting on a plane P, and denote by z the point that is diametrically opposite the point of contact of S and P. The mapping π : S \{z} → P, defined by π(s) = p if and only if the points z, s, and p are collinear, is called a stereographic projection from z; it is illustrated in Figure 10.5. z s p Fig. 10.5. Stereographic projection Theorem 10.4 A graph G is embeddable on the plane if and only if it is embeddable on the sphere. Proof Suppose that G has an embedding G on the sphere. Choose a point z of the sphere not in G. Then the image of G under stereographic projection from z is an embedding of G on the plane. The converse is proved similarly. On many occasions, it is advantageous to consider embeddings of planar graphs on the sphere; one instance is provided by the proof of Proposition 10.5 in the next section. Exercises 10.1.1 Show that: a) every proper subgraph of K3,3 is planar, b) K3,3 is nonplanar. 10.1.2 Show that a graph is planar if and only if every subdivision of the graph is planar
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 possibly 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
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 faces
10.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