Almost two decades have passed since the appearance of those graph theory texts that still set the agenda for most introductory courses taught today. The canon created by those books has helped to identify some main fields of study and research, and will doubtless continue to influence the development of the discipline for some time to come.

Preface

1. The Basics

 1.1 Graphs*

 1.2 The degree of a vertex*

 1.3 Paths and cycles*

 1.4 Connectivity*

 1.5 Trees and forests*

 1.6 Bipartite graphs*

 1.7 Contraction and minors*

 1.8 Euler tours*

 1.9 Some linear algebra

 1.10 Other notions of graphs

 Exercises

 Notes

2. Matching, Covering and Packing

 2.1 Matching in bipartite graphs*

 2.2 Matching in general graphs(*)

 2.3 Packing and covering

 2.4 Tree-packing and arboricity

 2.5 Path covers

 Exercises

 Notes

3. Connectivity

 3.1 2-Connected graphs and subgraphs*

 3.2 The structure of 3-connected graphs(*)

 3.3 Menger's theorem*

 3.4 Mader's theorem

 3.5 Linking pairs of vertices(*)

 Exercises

 Notes

4. Planar Graphs

 4.1 Topological prerequisites*

 4.2 Plane graphs*

 4.3 Drawings

 4.4 Planar graphs: Kuratowski's theorem*

 4.5 Algebraic planarity criteria

 4.6 Plane duality

 Exercises

 Notes

5. Colouring

 5.1 Colouring maps and planar graphs*

 5.2 Colouring vertices*

 5.3 Colouring edges*

 5.4 List colouring

 5.5 Perfect graphs

 Exercises

 Notes

6. Flows

 6.1 Circulations(*)

 6.2 Flows in networks*

 6.3 Group-valued flows

 6.4 k-Flows for small k

 6.5 Flow-colouring duality

 6.6 Tutte's flow conjectures

 Exercises

 Notes

7. Extremal Graph Theory

 7.1 Subgraphs*

 7.2 Minors(*)

 7.3 Hadwiger's conjecture*

 7.4 Szemeredi's regularity lemma

 7.5 Applying the regularity lemma

 Exercises

 Notes

8. Infinite Graphs

 8.1 Basic notions, facts and techniques*

 8.2 Paths, trees, and ends(*)

 8.3 Homogeneous and universal graphs*

 8.4 Connectivity and matching

 8.5 The topological end space

 Exercises

 Notes

9. Ramsey Theory for Graphs

 9.1 Ramsey's original theorems*

 9.2 Ramsey numbers(*)

 9.3 Induced Ramsey theorems

 9.4 Ramsey properties and connectivity(*)

 Exercises

 Notes

10. Hamilton Cycles

 10.1 Simple sufficient conditions*

 10.2 Hamilton cycles and degree sequences*

 10.3 Hamilton cycles in the square of a graph

 Exercises

 Notes

11. Random Graphs

 11.1 The notion of a random graph*

 11.2 The probabilistic method*

 11.3 Properties of almost all graphs*

 11.4 Threshold functions and second moments

 Exercises

 Notes

12. Minors, Trees and WQO

 12.1 Well-quasi-ordering*

 12.2 The graph minor theorem for trees*

 12.3 Tree-decompositions

 12.4 Tree-width and forbidden minors

 12.5 The graph minor theorem(*)

 Exercises

 Notes

A. Infinite sets

B. Surfaces

Hints for all the exercises

Index

Symbol index

Almost two decades have passed since the appearance of those graph theory texts that still set the agenda for most introductory courses taught today. The canon created by those books has helped to identify some main fields of study and research, and will doubtless continue to influence the development of the discipline for some time to come.
Yet much has happened in those 20 years, in graph theory no less than elsewhere： deep new theorems have been found, seemingly disparate methods and results have become interrelated, entire new branches have arisen. To name just a few such developments, one may think of how the new notion of list colouring has bridged the gulf between invuriants such as average degree and chromatic number, how probabilistic methods and the regularity lemma have pervaded extremai graph theory and Ramsey theory, or how the entirely new field of graph minors and tree-decompositions has brought standard methods of surface topology to bear on long-standing algorithmic graph problems.