Chapter Ⅰ Graphs and Subgraphs 1
Ⅰ.1 Definitions 1
Ⅰ.2 Isomorphism 5
Ⅰ.3 Subgraphs 9
Ⅰ.4 Vertices of attachment 11
Ⅰ.5 Components and connection 14
Ⅰ.6 Deletion of an edge 18
Ⅰ.7 Lists of nonisomorphic connected graphs 22
Ⅰ.8 Bridges 27
Ⅰ.9 Notes 30
Exercises 31
References 31
Chapter Ⅱ Contractions and the Theorem of Menger 32
Ⅱ.1 Contractions 32
Ⅱ.2 Contraction of an edge 37
Ⅱ.3 Vertices of attachment 41
Ⅱ.4 Separation numbers 43
Ⅱ.5 Menger's Theorem 46
Ⅱ.6 Hall's Theorem 50
Ⅱ.7 Notes 52
Exercises 53
References 53
Chapter Ⅲ 2-Connection 54
Ⅲ.1 Separable and 2-connected graphs 54
Ⅲ.2 Constructions for 2-connected graphs 56
Ⅲ.3 Blocks 60
Ⅲ.4 Arms 64
Ⅲ.5 Deletion and contraction of an edge 66
Ⅲ.6 Notes 68
Exercises 68
References 69
Chapter Ⅳ 3-Connection 70
Ⅳ.1 Multiple connection 70
Ⅳ.2 Some constructions for 3-connected graphs 74
Ⅳ.3 3-blocks 83
Ⅳ.4 Cleavages 95
Ⅳ.5 Deletions and contractions of edges 104
Ⅳ.6 The Wheel Theorem 111
Ⅳ.7 Notes 113
Exercises 114
References 114
Chapter Ⅴ Reconstruction 115
Ⅴ.1 The Reconstruction Problem 115
Ⅴ.2 Theory and practice 118
Ⅴ.3 Kelly's Lemma 119
Ⅴ.4 Edge-reconstruction 122
Ⅴ.5 Notes 123
Exercises 124
References 124
Chapter Ⅵ Digraphs and Paths 125
Ⅵ.1 Digraphs 125
Ⅵ.2 Paths 129
Ⅵ.3 The BEST Theorem 133
Ⅵ.4 The Matrix-Tree Theorem 138
Ⅵ.5 The Laws of Kirchhoff 142
Ⅵ.6 Identification of vertices 149
Ⅵ.7 Transportation Theory 152
Ⅵ.8 Notes 158
Exercises 159
References 159
Chapter Ⅶ Alternating Paths 161
Ⅶ.1 Cursality 161
Ⅶ.2 The bicursal subgraph 163
Ⅶ.3 Bicursal units 167
Ⅶ.4 Alternating barriers 168
Ⅶ.5 f-factors and f-barriers 170
Ⅶ.6 The f-factor theorem 174
Ⅶ.7 Subgraphs of minimum deficiency 178
Ⅶ.8 The bipartite case 180
Ⅶ.9 A theorem of Erd？s and Gallai 181
Ⅶ.10 Notes 183
Exercises 183
References 184
Chapter Ⅷ Algebraic Duality 185
Ⅷ.1 Chain-groups 185
Ⅷ.2 Primitive chains 188
Ⅷ.3 Regular chain-groups 194
Ⅷ.4 Cycles 197
Ⅷ.5 Coboundaries 200
Ⅷ.6 Reductions and contractions 204
Ⅷ.7 Algebraic duality 206
Ⅷ.8 Connectivity 209
Ⅷ.9 On transportation theory 215
Ⅷ.10 Incidence matrices 217
Ⅷ.11 Matroids 218
Ⅷ.12 Notes 219
Exercises 219
References 220
Chapter Ⅸ Polynomials Associated with Graphs 221
Ⅸ.1 V-functions 221
Ⅸ.2 The chromatic polynomial 226
Ⅸ.3 Colorings of graphs 233
Ⅸ.4 The flow polynomial 237
Ⅸ.5 Tait colorings 240
Ⅸ.6 The dichromate of a graph 243
Ⅸ.7 Some remarks on reconstruction 248
Ⅸ.8 Notes 250
Exercises 251
References 251
Chapter Ⅹ Combinatorial Maps 253
Ⅹ.1 Definitions and preliminary theorems 253
Ⅹ.2 Orientability 257
Ⅹ.3 Duality 259
Ⅹ.4 Isomorphism 261
Ⅹ.5 Drawings of maps 263
Ⅹ.6 Angles 268
Ⅹ.7 Operations on maps 268
Ⅹ.8 Combinatorial surfaces 275
Ⅹ.9 Cycles and coboundaries 281
Ⅹ.10 Notes 283
Exercises 284
References 284
Chapter Ⅺ Planarity 285
Ⅺ.1 Planar graphs 285
Ⅺ.2 Spanning subgraphs 288
Ⅺ.3 Jordan's Theorem 290
Ⅺ.4 Connectivity in planar maps 296
Ⅺ.5 The cross-cut Theorem 306
Ⅺ.6 Bridges 311
Ⅺ.7 An algorithm for planarity 314
Ⅺ.8 Peripheral circuitsin 3-connected graphs 317
Ⅺ.9 Kuratowski's Theorem 320
Ⅺ.10 Notes 325
Exercises 325
References 326
Index 327