xviContents1l. Random Graphs29311.1 The notion of a random graph29411.2 The probabilistic method*29911.3 Properties of almost all graphs*30211.4 Threshold functions and :....306na312ExerciseNotes31312. Minors, Trees and WQO31512.1 Well-quasi-ordering*...31612.2Thegraph31712.3 Tree-decompositio31932712.4Tree-widthandforbiddenminor12.5 The graph minor theorem(*)....341350ExercisesNotes354A. Infinite sets357B. Surfaces.361Hints for all the exerci..369Index393Sym409xvi Contents 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