xPrefaceAbout the second editionNaturally, I am delighted at having to write this addendum so soon afterthis book came out in the summer of 1997. It is particularly gratifyingto hear that people are gradually adopting it not only for their personaluse but more and more also as a course text; this, after all, was my aimwhen I wrote it, and my excuse for agonizing more over presentationthan I might otherwise have doneThere are two major changes. The last chapter on graph minorsnow gives a complete proof of one of the major results of the Robertson-Seymour theory, their theorem that excluding a graph as a minor boundsthe tree-width if and only if that graph is planar. This short proof didnot exist when I wrote the first edition, which is why Ithen included ashort proof of the next best thing, the analogous result for path-width.That theorem has now been dropped from Chapter 12. Another additionin this chapter is that the tree-width duality theorem, Theorem 12.3.9,now comes with a (short) proof too.The second major change is the addition of a complete set of hintsfor the exercises. These are largely Tommy Jensen's work, and I amgrateful for the time he donated to this project. The aim of these hintsis to help those who use the book to study graph theory on their own,but not to spoil the fun. The exercises, including hints, continue to beintended for classroom useApart from these two changes, there are a few additions. The mostnoticable of these are the formal introduction of depth-first search treesin Section 1.5 (which has led to some simplifications in later proofs) andan ingenious new proof of Menger's theorem due to Bohme, Goring andHarant (which has not otherwise been published)Finally, there is a host of small simplifications and clarificationsof arguments that I noticed as I taught from the book, or which werepointed out to me by others. To all these Ioffer my special thanks.The Web site for the book has followed me tohttp://www.math.uni-hamburg.de/home/diestel/books/graph.theory/I expect this address to be stable for some time.Once more, my thanks go to all who contributed to this secondedition by commenting on the firstand Ilook forward to further com-ments!RDDecember 1999x Preface About the second edition Naturally, I am delighted at having to write this addendum so soon after this book came out in the summer of 1997. It is particularly gratifying to hear that people are gradually adopting it not only for their personal use but more and more also as a course text; this, after all, was my aim when I wrote it, and my excuse for agonizing more over presentation than I might otherwise have done. There are two major changes. The last chapter on graph minors now gives a complete proof of one of the major results of the Robertson￾Seymour theory, their theorem that excluding a graph as a minor bounds the tree-width if and only if that graph is planar. This short proof did not exist when I wrote the first edition, which is why I then included a short proof of the next best thing, the analogous result for path-width. That theorem has now been dropped from Chapter 12. Another addition in this chapter is that the tree-width duality theorem, Theorem 12.3.9, now comes with a (short) proof too. The second major change is the addition of a complete set of hints for the exercises. These are largely Tommy Jensen’s work, and I am grateful for the time he donated to this project. The aim of these hints is to help those who use the book to study graph theory on their own, but not to spoil the fun. The exercises, including hints, continue to be intended for classroom use. Apart from these two changes, there are a few additions. The most noticable of these are the formal introduction of depth-first search trees in Section 1.5 (which has led to some simplifications in later proofs) and an ingenious new proof of Menger’s theorem due to B¨ohme, G¨oring and Harant (which has not otherwise been published). Finally, there is a host of small simplifications and clarifications of arguments that I noticed as I taught from the book, or which were pointed out to me by others. To all these I offer my special thanks. The Web site for the book has followed me to http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ I expect this address to be stable for some time. Once more, my thanks go to all who contributed to this second edition by commenting on the first—and I look forward to further com￾ments! December 1999 RD