1.The Basics 1
1.1 Graphs 2
1.2 The degree of a vertex 5
1.3 Paths and cycles 6
1.4 Connectivity 10
1.5 Trees and forests 13
1.6 Bipartite graphs 17
1.7 Contraction and minors 18
1.8 Euler tours 22
1.9 Some linear algebra 23
1.10 Other notions of graphs 28
Exercises 30
Notes 32
2.Matching，Covering and Packing 33
2.1 Matching in bipartite graphs 34
2.2 Matching in general graphs（*） 39
2.3 Packing and covering 44
2.4 Tree-packing and arboricity 46
2.5 Path covers 49
Exercises 51
Notes 53
3.Connectivity 55
3.1 2-Connected graphs and subgraphs 55
3.2 The structure of 3-connected graphs（*） 57
3.3 Menger’s theorem 62
3.4 Mader’s theorem 67
3.5 Linking pairs of vertices（*） 69
Exercises 78
Notes 80
4.Planar Graphs 83
4.1 Topological prerequisites 84
4.2 Plane graphs 86
4.3 Drawings 92
4.4 Planar graphs：Kuratowski’s theorem 96
4.5 Algebraic planarity criteria 101
4.6 Plane duality 103
Exercises 106
Notes 109
5.Colouring 111
5.1 Colouring maps and planar graphs 112
5.2 Colouring vertices 114
5.3 Colouring edges 119
5.4 List colouring 121
5.5 Perfect graphs 126
Exercises 133
Notes 136
6.Flows 139
6.1 Circulations（*） 140
6.2 Flows in networks 141
6.3 Group-valued flows 144
6.4 k-Flows for small k 149
6.5 Flow-colouring duality 152
6.6 Tntte’s flow conjectures 156
Exercises 160
Notes 161
7.Extremal Graph Theory 163
7.1 Subgraphs 164
7.2 Minors（*） 169
7.3 Hadwiger’s conjecture 172
7.4 Szemeredi’s regularity lemma 175
7.5 Applying the regularity lemma 183
Exercises 189
Notes 192
8.Infinite Graphs 195
8.1 Basic notions，facts and techniques 196
8.2 Paths，trees，and ends（*） 204
8.3 Homogeneous and universal graphs 212
8.4 Connectivity and matching 216
8.5 The topological end space 226
Exercises 237
Notes 244
9.Ramsey Theory for Graphs 251
9.1 Ramsey’s original theorems 252
9.2 Ramsey numbers（*） 255
9.3 Induced Ramsey theorems 258
9.4 Ramsey properties and connectivity（*） 268
Exercises 271
Notes 272
10.Hamilton Cycles 275
10.1 Simple sufficient conditions 275
10.2 Hamilton cycles and degree sequences 278
10.3 Hamilton cycles in the square of a graph 281
Exercises 289
Notes 290
11.Random Graphs 293
11.1 The notion of a random graph 294
11.2 The probabilistic method 299
11.3 Properties of almost all graphs 302
11.4 Threshold functions and second moments 306
Exercises 312
Notes 313
12.Minors，Trees and WQO 315
12.1 Well-quasi-ordering 316
12.2 The graph minor theorem for trees 317
12.3 Tree-decompositions 319
12.4 Tree-width and forbidden minors 327
12.5 The graph minor theorem（*） 341
Exercises 350
Notes 354
A.Infinite sets 357
B.Surfaces 361
Hints for all the exercises 369
Index 393
Symbol index 409