xviContents3. Connectivity59593.1 2-Connectedgraphsand sbgraph3.2The structure of 3-connected graphs(*62673.3Menger's theorem*...............3.4 Mader's theorem723.5 Link741182ExercisesNote4. Planar Graphs89904.1 Topological4.2Planegraphs*924.3Drawings984.4Planargraph02sistheor1074.5 Algebraic planarity criteria4.6 Plane duality110Exercises113*+++++ ++++++++++ +*++*+++Notes1175. Colouring1195.1 Colouring maps and planar graph201225.2 Colouring vertices*...................5.3 Colouring edges*1275.4.List colouring129+45.5 Perfect graphs135Exercise42Notes14626. Flows1491506.1 Circulations(6.2 Flows in networks*1516.3Grou154valued6.4 k-Flows for small k1596.5 Flow-colouring duality162....6.6 Tutte'sflow conject165169Exercises171xvi Contents 3. Connectivity .................................................... 59 3.1 2-Connected graphs and subgraphs* ............................ 59 3.2 The structure of 3-connected graphs(∗) .......................... 62 3.3 Menger’s theorem* ............................................. 67 3.4 Mader’s theorem ............................................... 72 3.5 Linking pairs of vertices(∗) ...................................... 74 Exercises ....................................................... 82 Notes .......................................................... 85 4. Planar Graphs .................................................. 89 4.1 Topological prerequisites* ...................................... 90 4.2 Plane graphs* .................................................. 92 4.3 Drawings ....................................................... 98 4.4 Planar graphs: Kuratowski’s theorem* .......................... 102 4.5 Algebraic planarity criteria ..................................... 107 4.6 Plane duality ................................................... 110 Exercises ....................................................... 113 Notes .......................................................... 117 5. Colouring ........................................................ 119 5.1 Colouring maps and planar graphs* ............................. 120 5.2 Colouring vertices* ............................................. 122 5.3 Colouring edges* ............................................... 127 5.4 List colouring .................................................. 129 5.5 Perfect graphs .................................................. 135 Exercises ....................................................... 142 Notes .......................................................... 146 6. Flows ............................................................ 149 6.1 Circulations(∗) .................................................. 150 6.2 Flows in networks* ............................................. 151 6.3 Group-valued flows ............................................. 154 6.4 k-Flows for small k ............................................. 159 6.5 Flow-colouring duality .......................................... 162 6.6 Tutte’s flow conjectures ........................................ 165 Exercises ....................................................... 169 Notes .......................................................... 171