xviliContents11. Random Graphs32311.1 The notion of a random gray.32411.2 The probabilistic method32933211.3 Properties of almost all graphs*33511.4 Threaoldfu.342ExerciseNotes34412. Graph Mir34712.1 Well34812.2The graph minor theorem for trees：34912.3Tree-cositions(*35112.4 Tree-width(*)... 35536012.5 Tar12.6Tre36912.7 The graph minor theorem(*)374Exercises382+++++*++..Notes388A. Infinite sets393B. SurfacesHints for all th407409IndeSymbol index427xviii Contents 11. Random Graphs ............................................... 323 11.1 The notion of a random graph* ................................. 324 11.2 The probabilistic method* ...................................... 329 11.3 Properties of almost all graphs* ................................ 332 11.4 Threshold functions and second moments ....................... 335 Exercises ....................................................... 342 Notes .......................................................... 344 12. Graph Minors ................................................. 347 12.1 Well-quasi-ordering(∗) ........................................... 348 12.2 The graph minor theorem for trees ............................. 349 12.3 Tree-decompositions(∗) .......................................... 351 12.4 Tree-width(∗) ................................................... 355 12.5 Tangles ........................................................ 360 12.6 Tree-decompositions and forbidden minors ...................... 369 12.7 The graph minor theorem(∗) .................................... 374 Exercises ....................................................... 382 Notes .......................................................... 388 A. Infinite sets ..................................................... 393 B. Surfaces ......................................................... 399 Hints for all the exercises............................................... 407 Index .................................................................. 409 Symbol index .......................................................... 427