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