U.S.R. MurtyJ.A. BondyGraph Theory (I) Springer
J.A. Bondy U.S.R. Murty Graph Theory (I) ABC
PrefaceFor more than one hundred years, the development of graph theory was inspiredby the Four-Colour Conjecture. The resolution of the conjectureandguided maiby K.Appel and W.Haken in1976, the yearin which ourfirst book Graph Theorywith Applications appeared, marked a turning point in its history. Since then, thesubject hasexperienced explosive growth, due in large measure to its role as anessential structurre underpinning modern applied mathematics. Computer scienceand combinatorial optimization, in particular, draw upon and contribute to thedevelopment of the theory of graphs. Moreover, in a world where communicationis of prime importance, the versatility of graphs makes them indispensable toolsinthe design and analysis of comnicationnetworksBuilding on the foundations laid by Claude Berge, Paul Erds, Bill Tutte, andothers, a new generation of graph-theorists has enriched and transformed the subject by developing powerful new techniques, many borrowed from other areas ofmathematics. These have led, in particular, to the resolution of several longstanding conjectures, including Berge's Strong Perfct Graph Conjecture and Kneser'sConjecture, both on colourings,and Gallai's Conjecture on cycle coverings.One of the dramatic developments over the past thirty years has been thecreation of the theory of graph minors by G. N. Robertson and P. D. Seyour.Ina long series of deep papers, they have revolutionized graph theory by introducingan original and incisive way of viewing graphical structure. Developed to attacka celebrated conjecture of K.Wagner, their theory gives incresotrembeddings of graphs in surfaces.It hasled alsoto polynomial-timealgorithmsfor solving avariety of hitherto intractable problems, such as that ofinding acollection of pairwise-disjoint paths between prescribed pairs of vertices.A technique which has met with spectacular success is the probabilistic method.Introduced in the 1940s by Erdos, in association with fellow Hungarians A. Renyiand PTuran,this powerful yet versatile tolis being employed withever-increasingfrequency andsophisticationtoestablishtheexistenceornonexistenceofgraphsand other combinatorial structures, with specified properties
Preface For more than one hundred years, the development of graph theory was inspired and guided mainly by the Four-Colour Conjecture. The resolution of the conjecture by K. Appel and W. Haken in 1976, the year in which our first book Graph Theory with Applications appeared, marked a turning point in its history. Since then, the subject has experienced explosive growth, due in large measure to its role as an essential structure underpinning modern applied mathematics. Computer science and combinatorial optimization, in particular, draw upon and contribute to the development of the theory of graphs. Moreover, in a world where communication is of prime importance, the versatility of graphs makes them indispensable tools in the design and analysis of communication networks. Building on the foundations laid by Claude Berge, Paul Erd˝os, Bill Tutte, and others, a new generation of graph-theorists has enriched and transformed the subject by developing powerful new techniques, many borrowed from other areas of mathematics. These have led, in particular, to the resolution of several longstanding conjectures, including Berge’s Strong Perfect Graph Conjecture and Kneser’s Conjecture, both on colourings, and Gallai’s Conjecture on cycle coverings. One of the dramatic developments over the past thirty years has been the creation of the theory of graph minors by G. N. Robertson and P. D. Seymour. In a long series of deep papers, they have revolutionized graph theory by introducing an original and incisive way of viewing graphical structure. Developed to attack a celebrated conjecture of K. Wagner, their theory gives increased prominence to embeddings of graphs in surfaces. It has led also to polynomial-time algorithms for solving a variety of hitherto intractable problems, such as that of finding a collection of pairwise-disjoint paths between prescribed pairs of vertices. A technique which has met with spectacular success is the probabilistic method. Introduced in the 1940s by Erd˝os, in association with fellow Hungarians A. R´enyi and P. Tur´an, this powerful yet versatile tool is being employed with ever-increasing frequency and sophistication to establish the existence or nonexistence of graphs, and other combinatorial structures, with specified properties
VIIIPrefaceAsremarked above, the growth of graph theory has been due in large measureto its essential rolein the applied sciences.In particular,the quesfor efficientalgorithmshasfuelledmuchresearchintothestructureofgraphs.Theimportanceof spanning trees of various special types, such as breadth-frst and depth-firsttrees, has become evident, and tree decompositions of graphs are a central ingredient in the theory of graph minors. Algorithmic graph theory borrows tools froma number of disciplines, including geometry and probability theory.The discoveryby S. Cook in the early 1970s of the existence of the extensive class of seeminglyintractable-NP-completeproblemshasledtothesearchfor.efficientapproxima-tion algorithms, the goal being to obtain a good approximation to the true valueHere again, probabilistic methods prove to be indispensable.The links between graph theory and other branches of mathematics are becom-ing increasingly strong, an indication of the growing maturity of the subject. Whave already noted certain connections with topology, geometry, and probability.Algebraicnalytic, and number-theoretic tools are also being employed to conserable effect. Conversely,graph-theoreticalmethods are being applied more andmore in other areas of mathematics. A notable example is Szemeredi's regularitylemma.Developed to solve a conjecture of Erdos and Turin, it has become anessential tool in additive number theory, as well as in extremal conbinatorics. Antensive account of this interplay can be found in the two-volume Handbook ofCombinatoricIt should be evident from the above remarks that graph theory is a fourishing discipline. It contains a body of beautiful and powerful theorems of wideapplicability. The remarkable growth of the subject is reflected in the wealth ofbooks and monogavailable. In addition to the Handbook of Combina-raphsnovtorics, much of which is devoted to graph theory, and the three-volume treatise oncombinatorial optimization by Schrijver (2003), destined to becomeaclassic.onecanfindmonographsoncolouringbyJensen andToft(1995)onfowsbyZhang1997)matching by Lovasz and Plur (1986), on extremal graph theory byBollobas (1978),on random graphs by Bollobas (2001) and Janson et al. (2000),on probabilistic methods by Alon and Spencer (2000)and Molloy and Reed (1998),on topological graph theory by Mohar and Thomassen (2001),on algebraic graphtheory by Biggs (1993), and on digraphs by Bang-Jensen and Gutin (2001), aswell as a good choice of textbooks. Another sign is the significantberofnewjournals dedicated to graph theoryThe present project began with the intention of simply making minor revisionsto our earlier book. However, we soon came to the realization that the changingface of the subject called for a total reornization and enhancement of its contents. As with Graph Theory with Applications, our primary aim here is to presenta coherent introduction tothe subject,suitable as atextbookfor advanced undergraduate and beginning graduate students in mathematics andcomputerscienceFor pedagogical reasons, we have concentrated on topics which can be coveredsatisfactorily in a course. The most conspicuousomission is the theory of graphminor,whichweonlytouchuonbeingtooompexobaccordedanadquat
VIII Preface As remarked above, the growth of graph theory has been due in large measure to its essential role in the applied sciences. In particular, the quest for efficient algorithms has fuelled much research into the structure of graphs. The importance of spanning trees of various special types, such as breadth-first and depth-first trees, has become evident, and tree decompositions of graphs are a central ingredient in the theory of graph minors. Algorithmic graph theory borrows tools from a number of disciplines, including geometry and probability theory. The discovery by S. Cook in the early 1970s of the existence of the extensive class of seemingly intractable N P-complete problems has led to the search for efficient approximation algorithms, the goal being to obtain a good approximation to the true value. Here again, probabilistic methods prove to be indispensable. The links between graph theory and other branches of mathematics are becoming increasingly strong, an indication of the growing maturity of the subject. We have already noted certain connections with topology, geometry, and probability. Algebraic, analytic, and number-theoretic tools are also being employed to considerable effect. Conversely, graph-theoretical methods are being applied more and more in other areas of mathematics. A notable example is Szemer´edi’s regularity lemma. Developed to solve a conjecture of Erd˝os and Tur´an, it has become an essential tool in additive number theory, as well as in extremal conbinatorics. An extensive account of this interplay can be found in the two-volume Handbook of Combinatorics. It should be evident from the above remarks that graph theory is a flourishing discipline. It contains a body of beautiful and powerful theorems of wide applicability. The remarkable growth of the subject is reflected in the wealth of books and monographs now available. In addition to the Handbook of Combinatorics, much of which is devoted to graph theory, and the three-volume treatise on combinatorial optimization by Schrijver (2003), destined to become a classic, one can find monographs on colouring by Jensen and Toft (1995), on flows by Zhang (1997), on matching by Lov´asz and Plummer (1986), on extremal graph theory by Bollob´as (1978), on random graphs by Bollob´as (2001) and Janson et al. (2000), on probabilistic methods by Alon and Spencer (2000) and Molloy and Reed (1998), on topological graph theory by Mohar and Thomassen (2001), on algebraic graph theory by Biggs (1993), and on digraphs by Bang-Jensen and Gutin (2001), as well as a good choice of textbooks. Another sign is the significant number of new journals dedicated to graph theory. The present project began with the intention of simply making minor revisions to our earlier book. However, we soon came to the realization that the changing face of the subject called for a total reorganization and enhancement of its contents. As with Graph Theory with Applications, our primary aim here is to present a coherent introduction to the subject, suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. For pedagogical reasons, we have concentrated on topics which can be covered satisfactorily in a course. The most conspicuous omission is the theory of graph minors, which we only touch upon, it being too complex to be accorded an adequate
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, Alexander
Preface 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 comments, 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 helpful material include Michael Albertson, Marcelo de Carvalho, Joseph Cheriyan, Roger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, Alexander
XPrefaceKelmans, Henry Kierstead, Laszlo Lovasz, Claudio Lucchesi, George Purdy, Di-eterRautenbach.BruceReed.BruceRichmond.NeilRobertson.Alexander Schrijver, Paul Seymour, Miklos Simonovits, Balazs Szegedy, Robin Thomas, StephanThommasse, Carsten Thomassen, and Jacques Verstraete. We thank them all warmlyfortheir various contributions. We are grateful also to Martin Crossley for allowingus to use (in Figure 10.24) drawings of the Mobius band and the torus taken fromhis book Crossley (2005).Facilities and support were kindly provided by Maurice Pouzet at UniversiteLyon 1 and Jean Fonlupt at Universite Paris 6. The glossary was prepared usingsoftware designed by Nicola Talbot of the University of East Anglia. Her promptlyoffered adviceappreciated.Finallywebenefittedfromafruitful relationship with Karen Borthwick at Springer,and from the technical help provided byher colleagues Brian Bishop and Frank Ganz.We are dedicating this book to the memory of our friends Claude Berge, PaulErdos, and BilTutteItowes its exstencetotheirachievements, theirguidinghands, and their personal kindness.J.A. Bondy and U.S.R. MurtySeptember 2007
X Preface Kelmans, Henry Kierstead, L´aszl´o Lov´asz, Cl´audio Lucchesi, George Purdy, Dieter Rautenbach, Bruce Reed, Bruce Richmond, Neil Robertson, Alexander Schrijver, Paul Seymour, Mikl´os Simonovits, Balazs Szegedy, Robin Thomas, St´ephan Thomass´e, Carsten Thomassen, and Jacques Verstra¨ete. We thank them all warmly for their various contributions. We are grateful also to Martin Crossley for allowing us to use (in Figure 10.24) drawings of the M¨obius band and the torus taken from his book Crossley (2005). Facilities and support were kindly provided by Maurice Pouzet at Universit´e Lyon 1 and Jean Fonlupt at Universit´e Paris 6. The glossary was prepared using software designed by Nicola Talbot of the University of East Anglia. Her promptlyoffered advice is much appreciated. Finally, we benefitted from a fruitful relationship with Karen Borthwick at Springer, and from the technical help provided by her colleagues Brian Bishop and Frank Ganz. We are dedicating this book to the memory of our friends Claude Berge, Paul Erd˝os, and Bill Tutte. It owes its existence to their achievements, their guiding hands, and their personal kindness. J.A. Bondy and U.S.R. Murty September 2007