Read the original document by opening this link in a new tab.
Table of Contents
Contents Preface to the fourth edition vii 1 Introduction 1 What is a graph? 1 2 Definitions and examples 2 Definition 8 3 Examples 17 4 Three puzzles 21 3 Paths and cycles 5 Connectivity 26 6 Eulerian graphs 31 7 Hamiltonian graphs 35 8 Some algorithms 38 4 Trees 9 Properties of trees 43 10 Counting trees 47 11 More applications 51 5 Planarity 12 Planar graphs 13 Euler's formula 60 14 Graphs on other surfaces 70 15 Dual graphs 73 16 Infinite graphs 77 6 Colouring graphs 17 Colouring vertices 81 18 Brooks' theorem 86 19 Colouring maps 88 20 Colouring edges 92 21 Chromatic polynomials 96 vi Contents 7 Digraphs 22 Definitions 100 23 Eulerian digraphs and tournaments 105 24 Markov chains 109 8 Matching, marriage and Menger's theorem 25 Hall's 'marriage' theorem 112 26 Transversal theory 115 27 Applications of Hall's theorem 118 28 Menger's theorem 122 29 Network flows 126 9 Matroids 30 Introduction to matroids 132 31 Examples of matroids 135 32 Matroids and graphs 139 33 Matroids and transversals 143 Appendix 147 Bibliography 148 Solutions to selected exercises 150 Index of symbols 167 Index of definitions 168
Summary
In recent years, graph theory has established itself as an important mathematical tool in a wide variety of subjects, ranging from operational research and chemistry to genetics and linguistics, and from electrical engineering and geography to sociology and architecture. At the same time it has also emerged as a worthwhile mathematical discipline in its own right. In view of this, there is a need for an inexpensive introductory text on the subject, suitable both for mathematicians taking courses in graph theory and also for non-specialists wishing to learn the subject as quickly as possible. It is my hope that this book goes some way towards filling this need. The only prerequisites to reading it are a basic knowledge of elementary set theory and matrix theory, although a further knowledge of abstract algebra is needed for more difficult exercises. The contents of this book may be conveniently divided into four parts. The first of these (Chapters 1-4) provides a basic foundation course, containing definitions and examples of graphs, connectedness, Eulerian and Hamiltonian paths and cycles, and trees. This is followed by two chapters (Chapters 5 and 6) on planarity and colouring, with special reference to the four-colour theorem. The third part (Chapters 7 and 8) deals with the theory of directed graphs and with transversal theory, with applications to critical path analysis, Markov chains and network flows. The book ends with a chapter on matroids (Chapter 9), which ties together material from the previous chapters and introduces some recent developments. Throughout the book I have attempted to restrict the text to basic material, using exercises as a means for introducing less important material. Of the 250 exercises, some are routine examples designed to test understanding of the text, while others will introduce you to new results and ideas. You should read each exercise, whether or not you work through it in detail. Difficult exercises are indicated by an asterisk. I have used the symbol // to indicate the end of a proof, and bold-face type is used for definitions. The number of elements in a set S is denoted by LSI, and the empty set is denoted by 0. A substantial number of changes have been made in this edition...