PrefaceAlmost twodecadeshave passed sincethe appearance of thosegraphtheory texts that still set the agenda for most introductory courses taughttodayThecanon created bythosebookshashelped toidentifysomen fields of study and research, and will doubtless continue to influence9the development of the discipline for some time to comeYet much has happened in those 20 years, in graph theory no lessthan elsewhere: deep new theorems have been found, seenlinglydisparatemethods and results have become interrelated, entire new branches havearisen. To name just a few such developments, one may think of howthe new notion of list colouring has bridged the gulf between invariants such as avedegree and chromatic number, how probabilisticmethods and the regularity lemma have pervaded extremal graph theoryand Ramsey theory, or how the entirely new field of graph minors andtree-decositionshasbrought standard methodsofsurfacetopologyto bear on long-standing algorithmic graph problems.Clearly,then,thetimehas comeforareappraisalwhat are,todaythessential areas, methods and results that should form the centre ofanintroductorygraphtheory courseaiming toequipits audiencefor themost likely developments ahead?I have tried in this book to offer material for such a course. Inview of the increasing complexity and maturity of the subject, I havebrokenwiththetraditionofattemptingtocoverboththeoryand applications: this book offers an introduction to the theory of graphs as partof (pure) mathematics; it contains neither explicit algorithms nor 'realworld' applications. My hope is that the potential for depth gained bythis restriction in scope will serve students of computer science8Smucas their peers in mathematics: assuming that they prefer algorithms butwillbenefitfromanencounterwithpuremathematicsofsomekind,itseems an ideal opportunity to look for this close to where their heart lies!In the selection and presentation of material, I have tried to ac-commodate two conficting goals. On the one hand, I believe that anPreface Almost two decades have passed since the appearance of those graph the￾ory 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 invari￾ants such as average degree and chromatic number, how probabilistic methods and the regularity lemma have pervaded extremal 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. Clearly, then, the time has come for a reappraisal: what are, today, the essential areas, methods and results that should form the centre of an introductory graph theory course aiming to equip its audience for the most likely developments ahead? I have tried in this book to offer material for such a course. In view of the increasing complexity and maturity of the subject, I have broken with the tradition of attempting to cover both theory and appli￾cations: this book offers an introduction to the theory of graphs as part of (pure) mathematics; it contains neither explicit algorithms nor ‘real world’ applications. My hope is that the potential for depth gained by this restriction in scope will serve students of computer science as much as their peers in mathematics: assuming that they prefer algorithms but will benefit from an encounter with pure mathematics of some kind, it seems an ideal opportunity to look for this close to where their heart lies! In the selection and presentation of material, I have tried to ac￾commodate two conflicting goals. On the one hand, I believe that an