Graduate Texts in Mathematics Editorial Board S. Axler F.W. Gehring K.A. Ribet Graduate Texts in Mathematics 1 TAKEUTI/ZARING. Introduction to 34 SPITZER. Principles of Random Walk. Axiomatic Set Theory. 2nd ed. 2nd ed. 2 OXTOBY. Measure and Category. 2nd ed. 35 ALEXANDER/WERMER. Several Complex 3 SCHAEFER. Topological Vector Spaces. Variables and Banach Algebras. 3rd ed. 2nd ed. 36 KELLEY/NAMIOKA et al. Linear 4 HILTON/STAMMBACH. A Course in Topological Spaces. Homological Algebra. 2nd ed. 37 MONK. Mathematical Logic. 5 MAC LANE. Categories for the Working 38 GRAUERT/FRITZSCHE. Several Complex Mathematician. 2nd ed. Variables. 6 HUGHES/PIPER. Projective Planes. 39 ARVESON. An Invitation to C*-Algebras. 7 J.-P. SERRE. A Course in Arithmetic. 40 KEMENY/SNELL/KNAPP. Denumerable 8 TAKEUTI/ZARING. Axiomatic Set Theory. Markov Chains. 2nd ed. 9 HUMPHREYS. Introduction to Lie Algebras 41 APOSTOL. Modular Functions and and Representation Theory. Dirichlet Series in Number Theory. 10 COHEN. A Course in Simple Homotopy 2nd ed. Theory. 42 J.-P. SERRE. Linear Representations of 11 CONWAY. Functions of One Complex Finite Groups. Variable I. 2nd ed. 43 GILLMAN/JERISON. Rings of Continuous 12 BEALS. Advanced Mathematical Analysis. Functions. 13 ANDERSON/FULLER. Rings and Categories 44 KENDIG. Elementary Algebraic Geometry. of Modules. 2nd ed. 45 LOEVE. Probability Theory I. 4th ed. 14 GOLUBITSKY/GUILLEMIN. Stable Mappings 46 LOEVE. Probability Theory II. 4th ed. and Their Singularities. 47 MOISE. Geometric Topology in 15 BERBERIAN. Lectures in Functional Dimensions 2 and 3. Analysis and Operator Theory. 48 SACHS/WU. General Relativity for 16 WINTER. The Structure of Fields. Mathematicians. 17 ROSENBLATT. Random Processes. 2nd ed. 49 GRUENBERG/WEIR. Linear Geometry. 18 HALMOS. Measure Theory. 2nd ed. 19 HALMOS. A Hilbert Space Problem Book. 50 EDWARDS. Fermat's Last Theorem. 2nd ed. 51 KLINGENBERG A Course in Differential 20 HUSEMOLLER. Fibre Bundles. 3rd ed. Geometry. 21 HUMPHREYS. Linear Algebraic Groups. 52 HARTSHORNE. Algebraic Geometry. 22 BARNES/MACK. An Algebraic Introduction 53 MANIN. A Course in Mathematical Logic. to Mathematical Logic. 54 GRAVER/WATKTNS. Combinatorics with 23 GREUB. Linear Algebra. 4th ed. Emphasis on the Theory of Graphs. 24 HOLMES. Geometric Functional Analysis 55 BROWN/PEARCY. Introduction to Operator and Its Applications. Theory I: Elements of Functional Analysis. 25 HEWITT/STROMBERG. Real and Abstract 56 MASSEY. Algebraic Topology: An Analysis. Introduction. 26 MANES. Algebraic Theories. 57 CROWELL/FOX. Introduction to Knot 27 KELLEY. General Topology. Theory. 28 ZARISKI/SAMUEL. Commutative Algebra. 58 KOBLITZ. p-adic Numbers, p-adic Vol.1. Analysis, and Zeta-Functions. 2nd ed. 29 ZARISKI/SAMUEL. Commutative Algebra. 59 LANG. Cyclotomic Fields. Vol.11. 60 ARNOLD. Mathematical Methods in 30 JACOBSON. Lectures in Abstract Algebra I. Classical Mechanics. 2nd ed. Basic Concepts. 61 WHITEHEAD. Elements of Homotopy 31 JACOBSON. Lectures in Abstract Algebra II. Theory. Linear Algebra. 62 KARGAPOLOV/MERLZJAKOV. Fundamentals 32 JACOBSON. Lectures in Abstract Algebra of the Theory of Groups. III. Theory of Fields and Galois Theory. 63 BOLLOBAS. Graph Theory. 33 HIRSCH. Differential Topology. (continued after index) Bela Bollobäs Modern Graph Theory With 118 Figures Springer Bela Bollobäs Trinity College Department of Mathematical Sciences University of Cambridge University of Memphis Cambridge CB2 1TQ 3725 Norriswood United Kingdom Memphis, TN 38152 [email protected] USA [email protected] Editorial Board S. Axler F.W. Gehring K.A. Ribet Mathematics Department Mathematics Department Mathematics Department San Francisco State East Hall University of California, University University of Michigan at Berkeley San Francisco, CA 94132 Ann Arbor, MI 48109 Berkeley, CA 94720-3840 USA USA USA Mathematics Subject Classification (2000): 05-01,05Cxx Library of Congress Cataloging-in-Publication Data Bollobäs, Bela. Modern graph theory / Bela Bollobäs. p. cm. — (Graduate texts in mathematics ; 184) Includes bibliographical references (p. - ) and index. ISBN 978-0-387-98488-9 ISBN 978-1-4612-0619-4 (eBook) DOI 10.1007/978-1-4612-0619-4 acid-free paper) 1. Graph Theory. I. Title. II. Series. QA166.B663 1998 511' .5—dc21 98-11960 ISBN 978-0-387-98488-9 Printed on acid-free paper. © 1998 Springer Science+Business Media New York Originally published by Springer Science+Business Media, Inc. in 1998 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher, Springer Science+Business Media, LLC. except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. 9 8 7 6 5 springeronline.com To Gabriella As long as a branch of science offers an abundance ofp roblems, so long is it alive; a lack of problems foreshadows extinction or the cessation of independent development. Just as any human undertaking pursues certain objects, so also mathematical research requires its problems. It is by the solution of problems that the investigator tests the temper of his steel; he finds new methods and new outlooks, and gains a wider and freer horizon. David Hilbert, Mathematical Problems, International Congress of Mathematicians, Paris, 1900. Apologia This book has grown out of Graph Theory - An Introductory Course (GT), a book I wrote about twenty years ago. Although I am still happy to recommend GT for a fairly fast-paced introduction to the basic results of graph theory, in the light of the developments in the past twenty years it seemed desirable to write a more substantial introduction to graph theory, rather than just a slightly changed new edition. In addition to the classical results of the subject from GT, amounting to about 40% of the material, this book contains many beautiful recent results, and also explores some of the exciting connections with other branches of mathematics that have come to the fore over the last two decades. Among the new results we discuss in detail are: Szemeredi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the results of Galvin and Thomassen on list colourings, the Perfect Graph Theorem of Lovasz and Fulkerson, and the precise description of the phase transition in the random graph process, extending the classical theorems of Erdos and Renyi. One whole field that has been brought into the light in recent years concerns the interplay between electrical networks, random walks on graphs, and the rapid mixing of Markov chains. Another important connection we present is between the Tutte polynomial of a graph, the partition functions of theoretical physics, and the powerful new knot polynomials. The deepening and broadening of the subject indicated by all the developments mentioned above is evidence that graph theory has reached a point where it should be treated on a par with all the well-established disciplines of pure mathematics. The time has surely now arrived when a rigorous and challenging course on the subject should be taught in every mathematics department. Another reason why graph theory demands prominence in a mathematics curriculum is its status as that branch of pure mathematics which is closest to computer science. This proximity enriches both disciplines: not only is graph theory fundamental to theoretical computer science, but problems arising in computer science and other areas of application greatly influence the direction taken by graph theory. In this book we shall not stress applications: our treatment of graph theory will be as an exciting branch of pure mathematics, full of elegant and innovative ideas. viii Apologia Graph theory, more than any other branch of mathematics, feeds on problems. There are a great many significant open problems which arise naturally in the subject: many of these are simple to state and look innocent but are proving to be surprisingly hard to resolve. It is no coincidence that Paul Erdos, the greatest problem-poser the world has ever seen, devoted much of his time to graph theory. This amazing wealth of open problems is mostly a blessing, but also, to some extent, a curse. A blessing, because there is a constant flow of exciting problems stimulating the development of the subject: a curse, because people can be misled into working on shallow or dead-end problems which, while bearing a superficial resemblence to important problems, do not really advance the subject. In contrast to most traditional branches of mathematics, for a thorough ground ing in graph theory, absorbing the results and proofs is only half of the battle. It is rare that a genuine problem in graph theory can be solved by simply applying an existing theorem, either from graph theory or from outside. More typically, solving a problem requires a "bare hands" argument together with a known re sult with a new twist. More often than not, it turns out that none of the existing high-powered machinery of mathematics is of any help to us, and nevertheless a solution emerges. The reader of this book will be exposed to many examples of this phenomenon, both in the proofs presented in the text and in the exercises. Needless to say, in graph theory we are just as happy to have powerful tools at our disposal as in any other branch of mathematics, but our main aim is to solve the substantial problems of the subject, rather than to build machinery for its own sake. Hopefully, the reader will appreciate the beauty and significance of the major results and their proofs in this book. However, tackling and solving a great many challenging exercises is an equally vital part of the process of becoming a graph theorist. To this end, the book contains an unusually large number of exercises: well over 600 in total. No reader is expected to attempt them all, but in order to really benefit from the book, the reader is strongly advised to think about a fair proportion of them. Although some of the exercises are straightforward, most of them are substantial, and some will stretch even the most able reader. Outside pure mathematics, problems that arise tend to lack a clear structure and an obvious line of attack. As such, they are akin to many a problem in graph theory: their solution is likely to require ingenuity and original thought. Thus the expertise gained in solving the exercises in this book is likely to pay dividends not only in graph theory and other branches of mathematics, but also in other scientific disciplines. "As long as a branch of science offers an abundance of problems, so long is it alive", said David Hilbert in his address to the Congress in Paris in 1900. Judged by this criterion, graph theory could hardly be more alive. B.B. Memphis March 15, 1998 Preface Graph theory is a young but rapidly maturing subject. Even during the quarter of a century that I lectured on it in Cambridge, it changed considerably, and I have found that there is a clear need for a text which introduces the reader not only to the well-established results, but to many of the newer developments as well. It is hoped that this volume will go some way towards satisfying that need. There is too much here for a single course. However, there are many ways of using the book for a single-semester course: after a little preparation any chapter can be included in the material to be covered. Although strictly speaking there are almost no mathematical prerequisites, the subject matter and the pace of the book demand mathematical maturity from the student. Each of the ten chapters consists of about five sections, together with a selection of exercises, and some bibliographical notes. In the opening sections of a chapter the material is introduced gently: much of the time results are rather simple, and the proofs are presented in detail. The later sections are more specialized and proceed at a brisker pace: the theorems tend to be deeper and their proofs, which are not always simple, are given rapidly. These sections are for the reader whose interest in the topic has been excited. We do not attempt to give an exhaustive list of theorems, but hope to show how the results come together to form a cohesive theory. In order to preserve the freshness and elegance of the material, the presentation is not over-pedantic: occasionally the reader is expected to formalize some details of the argument. Throughout the book the reader will discover connections with various other branches of mathematics, like optimization theory, group theory, matrix algebra, probability theory, logic, and knot theory. Although the reader is not expected to have intimate knowledge of these fields, a modest acquaintance with them would enhance the enjoyment of this book. The bibliographical notes are far from exhaustive: we are careful in our attribu tions of the major results, but beyond that we do little more than give suggestions for further readings. A vital feature of the book is that it contains hundreds of exercises. Some are very simple, and test only the understanding of the concepts, but many go way