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,whichweonlytouchuonbeingtooompexobaccordedanadquatVIII 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 ingre￾dient 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 approxima￾tion 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 becom￾ing 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 consid￾erable 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 flour￾ishing 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 Combina￾torics, 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 con￾tents. 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 under￾graduate 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