图论 第2版（影印版）

　　 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 invariants 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.
　　

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
2.1. matching in bipartite graphs
2.2. matching in general graphs
2.3. path covers
exercises
notes

　　 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 invariants 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.
　　 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 ofattempting to cover both theory and applications: 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 accommodate two conflicting goals. On the one hand, I believe that an introductory text should be lean and concentrate on the essential, so as to offer guidance to those new to the field. As a graduate text, moreover,
　　it should get to the heart of the matter quickly: after all, the idea is to convey at least an impression of the depth and methods of the subject.
　　On the other hand, it has been my particular concern to write with sufficient detail to make the text enjoyable and easy to read: guiding questions and ideas will be discussed explicitly, and all proofs presented will be rigorous and complete.
　　 A typical chapter, therefore, begins with a brief discussion of what are the guiding questions in the area it covers, continues with a succinct account of its classic results (often with simplified proofs), and then presents one or two deeper theorems that bring out the full fiavour of that area. The proofs of these latter results are typically preceded by (or
　　interspersed with) an informal account of their main ideas, but are then presented formally at the same level of detail as their simpler counterparts. I soon noticed that, as a consequence, some of those proofs came out rather longer in print than seemed fair to their often beautifully
　　simple conception. I would hope, however, that even for the professional reader the relatively detailed account of those proofs will at least help to minimize reading time...
　　 If desired, this text can be used for a lecture course with little or no further preparation. The simplest way to do this would be to follow the order of presentation, chapter by chapter: apart from two clearly marked exceptions, any results used in the proof of others precede them in the text.
　　 Alternatively, a lecturer may wish to divide the material into an easy .basic course for one semester, and a more challenging follow-up course for another. To help with the preparation of courses deviating from the order of presentation, I have listed in the margin next to each proof the reference numbers of those results that are used in that proof. These references are given in round brackets: for example, a reference (4.1.2) in the margin next to the proof Of Theorem 4.3.2 indicates that Lemma 4.1.2 will be used in this proof. Correspondingly, in the margin next to Lemma 4.1.2 there is a reference [4.3.2] (in square brackets) informing the reader that this lemma will be used in the proof of Theorem 4.3.2. Note that this system applies between different sections only (of the same or of different chapters): the sections themselves are written as units and best read in their order of presentation.
　　 The mathematical prerequisites for this book, as for most graph theory texts, are minimal: a first grounding in linear algebra is assumed for Chapter 1.9 and once in Chapter 5.5, some basic topological concepts about the Euclidean plane and 3-space are ased in Chapter 4, and
　　a previous first encounter with elementary probability will help with Chapter 11. (Even here, all that is assumed formally is the knowledge of basic definitions: the few probabilistic tools used are developed in the text.) There are two areas of graph theory which I find both fascinat-
　　ing and important, especially from the perspective of pure mathematics adopted here, but which are not covered in this book: these are algebraic graph theory and infinite graphs.
　　 At the end of each chapter, there is a section with exercises and another with bibliographical and historical notes. Many of the exercises were chosen to complement the main narrative of the text: they illus- ~trate new concepts, show how a new invariant relates to earlier ones,or indicate ways in which a result stated in the text is best possible.