ContentsGraphsSubgraphs3Connected GraphsTreesNonseparableGra17Tree-Search AlgorithmFlowsinNetwo157Complexity of Algori73Connectivity20510PlanarGrapl4:1l TheFour-Colour Problem12 Stable Sets and Cliqu9113TheProbabilisticMetho2514VertexColourin015Cole16Matching17 Edge ColouriContents 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