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
ContentsGraphsSubgraphs3Connected GraphsTreesNonseparableGra17Tree-Search AlgorithmFlowsinNetwo157Complexity of Algori73Connectivity20510PlanarGrapl4:1l TheFour-Colour Problem12 Stable Sets and Cliqu9113TheProbabilisticMetho2514VertexColourin015Cole16Matching17 Edge Colouri
Contents 1 Graphs ........................................................ 1 2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Connected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 Nonseparable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Tree-Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 9 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 11 The Four-Colour Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 12 Stable Sets and Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 13 The Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 14 Vertex Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 15 Colourings of Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 16 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 17 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
XIIContents18HamiltonCye19Covering1 DaclnDirerted Grar20 Electrical Netwo21IntegerUnsolvedProblenReferenceGraOperatioPFamiliesof Grap!sfDtHeNotatioIndex637
XII Contents 18 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 19 Coverings and Packings in Directed Graphs . . . . . . . . . . . . . . . . . . . 503 20 Electrical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 21 Integer Flows and Coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 Unsolved Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 General Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Graph Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 Operations and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 Families of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
1GraphsContents1.1 Graphs and TheRepresentation.................ANDEXAMPLES42DEBAE4SPECIALFAMILIESOFGRAPHS67INCIDENCEANDADJACENCYMATRICESVERTEX DEGREES1828PROOFTWOWAYS1.215and Automorphisms......oorons....EODTSAUTOMORPHISNABELLEDGRAPHS1.3GraphingfromOtherStructures....POLY+..INCIDENCE GRAPIINTERSECTIONGRAPHS1.4Constructing Graphs from Other Graphs .JNIONANDSCTION:RSA11.5Directed Graphs1.611Related Reading.SHISTORY OF GRAPH THEORY.1.1 Graphs and Their RepresentationDEFINITIONS AND EXAMPLESMany real-world situations can conveniently be described by means of a diagranconsistingof asetof pointstogetherwithlines joiningcertainpairs ofthesepoints
1 Graphs Contents 1.1 Graphs and Their Representation . ................. 1 Definitions and Examples ............................ 1 Drawings of Graphs ................................. 2 Special Families of Graphs .......................... 4 Incidence and Adjacency Matrices .................. 6 Vertex Degrees ..................................... 7 Proof Technique: Counting in Two Ways ............ 8 1.2 Isomorphisms and Automorphisms . . . . . . . . . . . . . . . . . 12 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Testing for Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Labelled Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Graphs Arising from Other Structures . . . . . . . . . . . . . 20 Polyhedral Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Set Systems and Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 21 Incidence Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Intersection Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 Constructing Graphs from Other Graphs . . . . . . . . . . . 29 Union and Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.5 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.6 Infinite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.7 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 History of Graph Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.1 Graphs and Their Representation Definitions and Examples Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points
21 GraphsFor example, the points could represent people, with lines joining pairs of friends; orcation centres.with lines repiepointsmightbecolcatiorglinks. Notice that in such diagrams one is mainly interested in whether two givenpoints are joined by a line; the manner in which they are joined is immaterial. Amathematical abstraction of situations of this type gives rise to the concept of agraph.A graph G is an ordered pair (V(G),E(G) consisting of a set V(G) of verticesand a set E(G), disjoint from V(G),of edges, together with an incidence functionWc that asciates with each edge of G anunordered pair of (not.necessarilydistinct) vertices of G. If e is an edge and u and are vertices such that bc(e) -[u.ul.the is said to joinuand w,and the vertices u and y are called the endsof e. We denote the numbers of vertices and edges in G by v(G) and e(G); thesetwobasicparametersarecalledtheorderand szeofGrespectivelyTwo examples of graphs should serve to clarify the definition. For notationalsimplicity, we write uu for the unordered pair [u,].Erample 1.G = (V(G),E(G)whereV(G)= fu,u,w,r,y)E(G) = (a,b,c,d,e, f,g,h)and wc is defined byve(a) = c(b) =uu c(c) =ww we(d)= wadc(e) = va c(f) = wr wc(g) =ur c(h) = ryErample 2.H =(V(H),E(H)whereV(H) = [o, 1, 2, U3, 4,05]E(H)- (e1e2,e,e,e,e,,es,e,and wh is defined bybh(ei)=uiu2 bh(e2) = u2us wr(es) =vau wh(es) = vaus bh(es)= Usuih(e6)= ouh(e7)=ou2 h(es)=Voua (eo)=Vou h(e10)=PovsDRAWINGS OF GRAPHSGraphs are so named because they can be represented graphically, and it is thisgraphical representation which helps us understand many of their properties. Eachvertex is indicated by a point, and each edge by a line joining the points representing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, verticesare represented by small circles.)
2 1 Graphs For example, the points could represent people, with lines joining pairs of friends; or the points might be communication centres, with lines representing communication links. Notice that in such diagrams one is mainly interested in whether two given points are joined by a line; the manner in which they are joined is immaterial. A mathematical abstraction of situations of this type gives rise to the concept of a graph. A graph G is an ordered pair (V (G),E(G)) consisting of a set V (G) of vertices and a set E(G), disjoint from V (G), of edges, together with an incidence function ψG that associates with each edge of G an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and u and v are vertices such that ψG(e) = {u,v}, then e is said to join u and v, and the vertices u and v are called the ends of e. We denote the numbers of vertices and edges in G by v(G) and e(G); these two basic parameters are called the order and size of G, respectively. Two examples of graphs should serve to clarify the definition. For notational simplicity, we write uv for the unordered pair {u,v}. Example 1. G = (V (G),E(G)) where V (G) = {u,v,w,x,y} E(G) = {a,b,c,d,e,f,g,h} and ψG is defined by ψG(a) = uv ψG(b) = uu ψG(c) = vw ψG(d) = wx ψG(e) = vx ψG(f) = wx ψG(g) = ux ψG(h) = xy Example 2. H = (V (H),E(H)) where V (H) = {v0,v1,v2,v3,v4,v5} E(H) = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10} and ψH is defined by ψH(e1) = v1v2 ψH(e2) = v2v3 ψH(e3) = v3v4 ψH(e4) = v4v5 ψH(e5) = v5v1 ψH(e6) = v0v1 ψH(e7) = v0v2 ψH(e8) = v0v3 ψH(e9) = v0v4 ψH(e10) = v0v5 Drawings of Graphs Graphs are so named because they can be represented graphically, and it is this graphical representation which helps us understand many of their properties. Each vertex is indicated by a point, and each edge by a line joining the points representing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, vertices are represented by small circles.)
1.1 Graphs and Their RepresentatiorFig, 1.1. Diagrams of the graphs G and HThere is no single correct way to draw a graph: the relative positions of pointsrepresenting vertices and the shapes of lines representing edges usually have nosignificance. In Figure 1.l, the edges of G are depicted by curves, and those ofH by straight-lirle segments. A diagram of a graph merely depicts the incidencerelation holding between its vertices and edges. However, we often draw a diagramof a graph and refer to it as the graph itself; in the same spirit, we call its points'vertices' and its lines 'edges'.Most of the definitions and concepts in graph theory are suggested by thisgraphical representation. The ends of an edge are said to be incident with theedge, and vice versa. Two vertices which are incident with a common edge areadjacent, as are two edges which are incident with a common vertex, and twodistincadjacentverticneighbours. The set of neighbours of a vertex v in agraph G is denoted by Nc(o)An edgewithidentical erds is called a loop, and an edge with distendslink.Twoormorelinks withthesamepairofends aresaid tobe parllel edges.Inthe graph G of Figure 1.l, the edge b is a loop, and all other edges are links; theedges d and f are parallel edgesThroughout the book, the letter G denotes a graph. Moreover, when there isno scope for ambiguity,we omittheletterGfromgraph-theoreticsymbols andwrite, for example, V and E instead of V(G) and E(G). In such instances, wedenotethenumbers ofvertices and edgesof G by n andm,respectivelyA graph is finite if both its vertex set and edge set are finite. In this book, wmainle graphs, and the ternmgraph'always meanss 'finite graph'. TheICVgraph with no vertices (and hence no edges) is the null graph. Any graph with justone vertex is referred to as trivial. All other graphs are nontrivial. We admit thenull graph solely for mathematical convenience. Thus, unless otherwise specified,all graphs under discussion should be taken to be nonnullA graph is simple if it has no loops or parallel edges. The graph H in Example 2is simple, whereas the graph G in Example 1 is not. Much of graph theory isconcerned with thestudy of simplegraphs
1.1 Graphs and Their Representation 3 v0 v1 v2 v4 v3 v5 e1 e2 e3 e4 e5 e6 e7 e9 e8 e10 G u v x w y a b c d e f g h H Fig. 1.1. Diagrams of the graphs G and H There is no single correct way to draw a graph; the relative positions of points representing vertices and the shapes of lines representing edges usually have no significance. In Figure 1.1, the edges of G are depicted by curves, and those of H by straight-line segments. A diagram of a graph merely depicts the incidence relation holding between its vertices and edges. However, we often draw a diagram of a graph and refer to it as the graph itself; in the same spirit, we call its points ‘vertices’ and its lines ‘edges’. Most of the definitions and concepts in graph theory are suggested by this graphical representation. The ends of an edge are said to be incident with the edge, and vice versa. Two vertices which are incident with a common edge are adjacent, as are two edges which are incident with a common vertex, and two distinct adjacent vertices are neighbours. The set of neighbours of a vertex v in a graph G is denoted by NG(v). An edge with identical ends is called a loop, and an edge with distinct ends a link. Two or more links with the same pair of ends are said to be parallel edges. In the graph G of Figure 1.1, the edge b is a loop, and all other edges are links; the edges d and f are parallel edges. Throughout the book, the letter G denotes a graph. Moreover, when there is no scope for ambiguity, we omit the letter G from graph-theoretic symbols and write, for example, V and E instead of V (G) and E(G). In such instances, we denote the numbers of vertices and edges of G by n and m, respectively. A graph is finite if both its vertex set and edge set are finite. In this book, we mainly study finite graphs, and the term ‘graph’ always means ‘finite graph’. The graph with no vertices (and hence no edges) is the null graph. Any graph with just one vertex is referred to as trivial. All other graphs are nontrivial. We admit the null graph solely for mathematical convenience. Thus, unless otherwise specified, all graphs under discussion should be taken to be nonnull. A graph is simple if it has no loops or parallel edges. The graph H in Example 2 is simple, whereas the graph G in Example 1 is not. Much of graph theory is concerned with the study of simple graphs