Graph Theory Third EditionPDF电子书下载

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