Ⅰ Fundamentals 1
Ⅰ.1 Definitions 1
Ⅰ.2 Paths，Cycles，and Trees 8
Ⅰ.3 Hamilton Cycles and Euler Circuits 14
Ⅰ.4 Planar Graphs 20
Ⅰ.5 An Application of Euler Trails to Algebra 25
Ⅰ.6 Exercises 28
Ⅱ Electcical Networks 39
Ⅱ.1 Graphs and Electrical Networks 39
Ⅱ.2 Squaring the Square 46
Ⅱ.3 Vector Spaces and Matrices Associated with Graphs 51
Ⅱ.4 Exercises 58
Ⅱ.5 Notes 66
Ⅲ Flows，Connectivity and Matching 67
Ⅲ.1 Flows in Directed Graphs 68
Ⅲ.2 Connectivity and Menger’s Theorem 73
Ⅲ.3 Matching 76
Ⅲ.4 Tutte’s 1-Factor Theorem 82
Ⅲ.5 Stable Matchings 85
Ⅲ.6 Exercises 91
Ⅲ.7 Notes 101
Ⅳ Extremal Problems 103
Ⅳ.1 Paths and Cycles 104
Ⅳ.2 Complete Subgraphs 108
Ⅳ.3 Hamilton Paths and Cycles 115
Ⅳ.4 The Structure of Graphs 120
Ⅳ.5 Szemeredi’s Regularity Lemma 124
Ⅳ.6 Simple Applications of Szemeredi’s Lemma 130
Ⅳ.7 Exercises 135
Ⅳ.8 Notes 142
Ⅴ Colouring 145
Ⅴ.1 Vertex Colouring 146
Ⅴ.2 Edge Colouring 152
Ⅴ.3 Graphs on Surfaces 154
Ⅴ.4 List Colouring 161
Ⅴ.5 Perfect Graphs 165
Ⅴ.6 Exercises 170
Ⅴ.7 Notes 177
Ⅵ Ramsey Theory 181
Ⅵ.1 The Fundamental Ramsey Theorems 182
Ⅵ.2 Canonical Ramsey Theorems 189
Ⅵ.3 Ramsey Theory For Graphs 192
Ⅵ.4 Ramsey Theory for Integers 197
Ⅵ.5 Subsequences 205
Ⅵ.6 Exercises 208
Ⅵ.7 Notes 213
Ⅶ Random Graphs 215
Ⅶ.1 The Basic Models—The Use of the Expectation 216
Ⅶ.2 Simple Properties of Almost All Graphs 225
Ⅶ.3 Almost Determined Variables—The Use of the Variance 228
Ⅶ.4 Hamilton Cycles—The Use of Graph Theoretic Tools 236
Ⅶ.5 The Phase Transition 240
Ⅶ.6 Exercises 246
Ⅶ.7 Notes 251
Ⅷ Graphs，Groups and Matrices 253
Ⅷ.1 Cayley and Schreier Diagrams 254
Ⅷ.2 The Adjacency Matrix and the Laplacian 262
Ⅷ.3 Strongly Regular Graphs 270
Ⅷ.4 Enumeration and P6lya’s Theorem 276
Ⅷ.5 Exercises 283
Ⅸ Random Walks on Graphs 295
Ⅸ.1 Electrical Networks Revisited 296
Ⅸ.2 Electrical Networks and Random Walks 301
Ⅸ.3 Hitting Times and Commute Times 309
Ⅸ.4 Conductance and Rapid Mixing 319
Ⅸ.5 Exercises 327
Ⅸ.6 Notes 333
X The Tutte Polynomial 335
X.1 Basic Properties of the Tutte Polynomial 336
X.2 The Universal Form of the Tutte Polynomial 340
X.3 The Tutte Polynomial in Statistical Mechanics 342
X.4 Special Values of the Tutte Polynomial 345
X.5 A Spanning Tree Expansion of the Tutte Polynomial 350
X.6 Polynomials of Knots and Links 358
X.7 Exercises 371
X.8 Notes 377
Symbol Index 379
Name Index 383
Subject Index 387