J.A. BondyU.S.R. MurtyGraph Theory (III) Springer
J.A. Bondy U.S.R. Murty Graph Theory ABC Graph Theory (III)
ContentsGraphs11ed GraphTreesNonoleGrsSerTree-Search A35FlowsinNetw57omplexitAlg73lectivit0510PlanarGraph2431l TheFour-Colour Probler12Stable Sets and Cliqu9113TheProbabilisticMeth2514 VertexC015Cole16Matching17Edge Colour
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
XIIContents18 Hamilton Cycles47119 Coverings and Packings in Directed Graph50320 Electrical Networks52721IntegerFlowanco557Unsolved Problems08.References.GenealMath623Graph Pa625Operations and Relat627Families of Graphs629Struct631OtherNotatiol03Index637
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
18Hamilton CyclesContentsTOUGHGRAPHS+HYPOHAMILTON18.2 NonhamilttonianPlanarGraphsBERG'ST+++++..++BARNETTE'S CONJE18.3 Path and Cycle ExchangePATHEXCHANGECYCLE EXCHANGESDIRAC'S THEOREMTHE CLOSURE OF A GRAPHTHE CHVATAL-ERDOSTHEOREM18.4 Path Exchanges and ParityTHELOLLIPOPLEMMAUNIQUELY HAMILTONIAN GRAPHSSHEEHAN'S CONJECTURE18.5 HamiCyclesinRm Graphs......OSAOSR18.6 Related Reading.BRIDGETHE HOPPING LEMLONG PATHS AND CYCLES18.1 Hamiltonian and Nonhamiltonian GraphsRecall that a path or cycle which contains every vertex of a graph is called aHamiltonpathor Hamiltoncycleof thegraph.Suchpathsand cycles arenamecafterSirWilliamRowanHamilton,whodescribed,inalettertohisfriendGravesin 1856, a mathematical game on the dodecahedron (Figure 18.la) in which one
18 Hamilton Cycles Contents 18.1 Hamiltonian and Nonhamiltonian Graphs . . . . . . . . . . 471 Tough Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 Hypohamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 18.2 Nonhamiltonian Planar Graphs . . . . . . . . . . . . . . . . . . . . 478 Grinberg’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Barnette’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 18.3 Path and Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . 483 Path Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Dirac’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 The Closure of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 The Chvatal–Erd ´ os Theorem ˝ . . . . . . . . . . . . . . . . . . . . . . . . 488 18.4 Path Exchanges and Parity . . . . . . . . . . . . . . . . . . . . . . . . 492 The Lollipop Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Uniquely Hamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . 494 Sheehan’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 18.5 Hamilton Cycles in Random Graphs . . . . . . . . . . . . . . . 499 Posa’s Lemma ´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 18.6 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Bridge Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Hopping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 Long Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 18.1 Hamiltonian and Nonhamiltonian Graphs Recall that a path or cycle which contains every vertex of a graph is called a Hamilton path or Hamilton cycle of the graph. Such paths and cycles are named after Sir William Rowan Hamilton, who described, in a letter to his friend Graves in 1856, a mathematical game on the dodecahedron (Figure 18.1a) in which one
47218 Hamilton Cyclesperson sticks pins in any five consecutive vertices and the other is required to comlottlformed to a spanning cycle (see Biggs et al. (1986) or Hamilton(1931). Hamilton was prompted to consider such cycles in his early investigationsinto group theory, the three edges incident to a vertex corresponding to threegenerators of a groupA graph is traceable if it contains a Hamilton path, and hamiltonian if it contains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle isindicated inFigure18.la.On the other hand,the Herschel graphof Figure18.1bis nonhamiltonian, because it is bipartite and has an odd number of vertices. Thisgraph is, however, traceable(a)(b)Fig. 18.1. Hamiltonian and nonhanmiltonian graphs: (a) the dodecahedron, (b) the Herschel graphTOUGH GRAPHSAs we saw in Section 8.3, the problem of deciding whether a given graph is hamiltonian is NP-complete. It is therefore natural to look for reasonable necessarysufficient conditions for the existence of Hamilton cycles. The following simplenecessary condition turns out to be surprisingly useful.Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then(18.1)c(G - S) ≤ISIMoreover, if equality holds in (18.1), then each of the [S] components of G -2tracableandeeryHamiltoncyceGincludsHamitonpathiachfthcomponents.Proof Let C be a Hamilton cycle of G. Then C - S clearly has at most [SlOnents. But this implies that G- S also has at most Js] components, becauseC is a spanning subgraph of G
472 18 Hamilton Cycles person sticks pins in any five consecutive vertices and the other is required to complete the path so formed to a spanning cycle (see Biggs et al. (1986) or Hamilton (1931)). Hamilton was prompted to consider such cycles in his early investigations into group theory, the three edges incident to a vertex corresponding to three generators of a group. A graph is traceable if it contains a Hamilton path, and hamiltonian if it contains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle is indicated in Figure 18.1a. On the other hand, the Herschel graph of Figure 18.1b is nonhamiltonian, because it is bipartite and has an odd number of vertices. This graph is, however, traceable. (a) (b) Fig. 18.1. Hamiltonian and nonhamiltonian graphs: (a) the dodecahedron, (b) the Herschel graph Tough Graphs As we saw in Section 8.3, the problem of deciding whether a given graph is hamiltonian is N P-complete. It is therefore natural to look for reasonable necessary or sufficient conditions for the existence of Hamilton cycles. The following simple necessary condition turns out to be surprisingly useful. Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then c(G − S) ≤ |S| (18.1) Moreover, if equality holds in (18.1), then each of the |S| components of G − S is traceable, and every Hamilton cycle of G includes a Hamilton path in each of these components. Proof Let C be a Hamilton cycle of G. Then C − S clearly has at most |S| components. But this implies that G−S also has at most |S| components, because C is a spanning subgraph of G