IXPrefacetreatment. We have maintained as far as possible the terminology and notation ofOour earlier book, which are now generally accepted.Particular carehas been taken to provideasystematictreatentofthetheoof graphs without sacrificing its intaesthetic appeal. Commonly usedtuutiveproof techniques are described and llustrated. Many of these are to be found ininsets, whereas others, such as search trees, network flows, the regularity lemmaand the local lemm are the topics of entire sections or chapters. The exercises,of varying levels of dficulty, have been designed so as to help the reader masterthese techniques and to reinforce his or her grasp of the material. Those exerciseswhich are needed for an understanding of the text are indicated by a star. Themore challenginer ones by a dividing line.orsesareseparatedfromtheeasieeA second objective of the book is to serve as an introduction to research ingraph theory. To this end, sections on more advanced topics are included, and anumber of interesting and challenging open problems are highlighted and discussedin some detail. These and many more are listed in an appendix.Despitethismore advanced material, the book has beeized insucha wahate ongraph theory may be based onthefirst few sectiontroductorycoulofsedchapersLikumbrthryraphhoryonuallympegives rise to challenging unsolved problems. Like geometry, it is visually pleasingThsewoatsalongwith itsdivereappicationmakraphthryanidasubject for inclusion in mathematical curricula.We have sought to convey the aesthetic appeal of graph theory by illustratingthe text with many interesting graphs - a full list can be found in the indexThe cover design, taken from Chapter 10, depicts simultaneous embeddings on theprojective plane of Ke and its dual, the Petersengraph.A Web page for the book is available athttp://blogs.springer.com/bondyandmurtyThereader willfind therehints to selected exerses, background to open problemsother supplementary material, and an inevitable list of errata. For instructorswishing to use the b as the basis for a course, suggestions are provided as toan appropriate selection of topics, depending on the intended audience.We are indebted to many friends and colleagues for their interest in andhelp with this project. Tommy Jensen deserves a special word of thanks. Heread through the entire manuscript, provided numerous unfailingly pertinent conments, simplified and clarified several proofs, corrected many technical errors andlinguistic infelicities, and made valuable suggestions. Others who went throughand commented on parts of the book include Noga Alon, Roland Assous, XavierBuchwalder, Genghua Fan, Frederic Havet, Bill Jackson, Stephen Locke, ZsoltTuza, and two anonymous readers. We were most fortunate to benefit in this wayfrom their excellent knowledge and tasteColleagues whooffered adviceor supplied exercises.problems,and otherhelpful material include Michael Albertson,Marcelo de Carvalho.Joseph CheriyanRoger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, AlexanderPreface IX treatment. We have maintained as far as possible the terminology and notation of our earlier book, which are now generally accepted. Particular care has been taken to provide a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated. Many of these are to be found in insets, whereas others, such as search trees, network flows, the regularity lemma and the local lemma, are the topics of entire sections or chapters. The exercises, of varying levels of difficulty, have been designed so as to help the reader master these techniques and to reinforce his or her grasp of the material. Those exercises which are needed for an understanding of the text are indicated by a star. The more challenging exercises are separated from the easier ones by a dividing line. A second objective of the book is to serve as an introduction to research in graph theory. To this end, sections on more advanced topics are included, and a number of interesting and challenging open problems are highlighted and discussed in some detail. These and many more are listed in an appendix. Despite this more advanced material, the book has been organized in such a way that an introductory course on graph theory may be based on the first few sections of selected chapters. Like number theory, graph theory is conceptually simple, yet gives rise to challenging unsolved problems. Like geometry, it is visually pleasing. These two aspects, along with its diverse applications, make graph theory an ideal subject for inclusion in mathematical curricula. We have sought to convey the aesthetic appeal of graph theory by illustrating the text with many interesting graphs — a full list can be found in the index. The cover design, taken from Chapter 10, depicts simultaneous embeddings on the projective plane of K6 and its dual, the Petersen graph. A Web page for the book is available at http://blogs.springer.com/bondyandmurty The reader will find there hints to selected exercises, background to open problems, other supplementary material, and an inevitable list of errata. For instructors wishing to use the book as the basis for a course, suggestions are provided as to an appropriate selection of topics, depending on the intended audience. We are indebted to many friends and colleagues for their interest in and help with this project. Tommy Jensen deserves a special word of thanks. He read through the entire manuscript, provided numerous unfailingly pertinent com￾ments, simplified and clarified several proofs, corrected many technical errors and linguistic infelicities, and made valuable suggestions. Others who went through and commented on parts of the book include Noga Alon, Roland Assous, Xavier Buchwalder, Genghua Fan, Fr´ed´eric Havet, Bill Jackson, Stephen Locke, Zsolt Tuza, and two anonymous readers. We were most fortunate to benefit in this way from their excellent knowledge and taste. Colleagues who offered advice or supplied exercises, problems, and other help￾ful material include Michael Albertson, Marcelo de Carvalho, Joseph Cheriyan, Roger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, Alexander