Introduction to Graph Theory
, by West, Douglas B.Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
 ISBN: 9780130144003  0130144002
 Cover: Hardcover
 Copyright: 8/22/2000
This book fills a need for a thorough introduction to graph theory that features both the understanding and writing of proofs about graphs. Verification that algorithms work is emphasized more than their complexity.An effective use of examples, and huge number of interesting exercises, demonstrate the topics of trees and distance, matchings and factors, connectivity and paths, graph coloring, edges and cycles, and planar graphs.For those who need to learn to make coherent arguments in the fields of mathematics and computer science.
Preface  xi  

1  (66)  

1  (18)  

1  (2)  

3  (3)  

6  (5)  

11  (3)  

14  (5)  

19  (15)  

20  (4)  

24  (2)  

26  (5)  

31  (3)  

34  (19)  

35  (3)  

38  (6)  

44  (3)  

47  (6)  

53  (14)  

53  (5)  

58  (2)  

60  (1)  

61  (2)  

63  (4)  

67  (40)  

67  (14)  

68  (2)  

70  (3)  

73  (2)  

75  (6)  

81  (14)  

81  (2)  

83  (4)  

87  (2)  

89  (3)  

92  (3)  

95  (12)  

95  (2)  

97  (3)  

100  (3)  

103  (4)  

107  (42)  

107  (16)  

108  (2)  

110  (2)  

112  (1)  

113  (3)  

116  (2)  

118  (5)  

123  (13)  

123  (2)  

125  (5)  

130  (2)  

132  (2)  

134  (2)  

136  (13)  

136  (4)  

140  (2)  

142  (3)  

145  (4)  

149  (42)  

149  (12)  

149  (3)  

152  (3)  

155  (3)  

158  (3)  

161  (15)  

161  (3)  

164  (2)  

166  (4)  

170  (2)  

172  (4)  

176  (15)  

176  (5)  

181  (3)  

184  (4)  

188  (3)  

191  (42)  

191  (13)  

191  (3)  

194  (3)  

197  (2)  

199  (5)  

204  (15)  

205  (2)  

207  (3)  

210  (2)  

212  (2)  

214  (5)  

219  (14)  

219  (5)  

224  (2)  

226  (2)  

228  (1)  

229  (4)  

233  (40)  

233  (13)  

233  (3)  

236  

241  (2)  

243  (3)  

246  (11)  

247  (1)  

248  (4)  

252  (3)  

255  (2)  

257  (16)  

257  (4)  

261  (5)  

266  (3)  

269  (4)  

273  (46)  

273  (13)  

274  (5)  

279  (3)  

282  (4)  

286  (13)  

287  (1)  

288  (5)  

293  (1)  

294  (5)  

299  (20)  

300  (2)  

302  (2)  

304  (3)  

307  (7)  

314  (5)  

319  (152)  

319  (30)  

320  (3)  

323  (5)  

328  (6)  

334  (6)  

340  (4)  

344  (5)  

349  (29)  

349  (5)  

354  (4)  

358  (2)  

360  (3)  

363  (3)  

366  (3)  

369  (3)  

372  (6)  

378  (18)  

378  (2)  

380  (3)  

383  (3)  

386  (2)  

388  (4)  

392  (4)  

396  (29)  

397  (7)  

404  (4)  

408  (5)  

413  (3)  

416  (6)  

422  (3)  

425  (27)  

426  (4)  

430  (2)  

432  (4)  

436  (3)  

439  (3)  

442  (6)  

448  (4)  

452  (19)  

453  (3)  

456  (2)  

458  (2)  

460  (3)  

463  (1)  

464  (3)  

467  (4)  
Appendix A Mathematical Background  471  (22)  

471  (4)  

475  (4)  

479  (4)  

483  (2)  

485  (4)  

489  (2)  

491  (2)  
Appendix B Optimization and Complexity  493  (14)  

493  (3)  

496  (3)  

499  (6)  

505  (2)  
Appendix C Hints for Selected Exercises  507  (8)  

507  (1)  

508  (7)  
Appendix D Glossary of Terms  515  (18)  
Appendix E Supplemental Reading  533  (34)  
Appendix F References  567  (2)  
Author Index  569  (6)  
Subject Index  575 
PrefaceGraph theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. The design of this book permits usage in a onesemester introduction at the undergraduate or beginning graduate level, or in a patient twosemester introduction. No previous knowledge of graph theory is assumed. Many algorithms and applications are included, but the focus is on understanding the structure of graphs and the techniques used to analyze problems in graph theory.Many textbooks have been written about graph theory. Due to its emphasis on both proofs and applications, the initial model for this book was the elegant text by J.A. Bondy and US.R. Murty,Graph Theory with Applications(Macmillan/NorthHolland 1976). Graph theory is still young, and no consensus has emerged on how the introductory material should be presented. Selection and order of topics, choice of proofs, objectives, and underlying themes are matters of lively debate. Revising this book dozens of times has taught me the difficulty of these decisions. This book is my contribution to the debate. The Second EditionThe revision for the second edition emphasizes making the text easier for the students to learn from and easier for the instructor to teach from. There have not been great changes in the overall content of the book, but the presentation has been modified to make the material more accessible, especially in the early parts of the book. Some of the changes are discussed in more detail later in this preface; here I provide a brief summary. Optional material within nonoptional sections is now designated by (*); such material is not used later and can be skipped. Most of it isintendedto be skipped in a onesemester course. When a subsection is marked "optional", the entire subsection is optional, and hence no individual items are starred. For lessexperienced students, Appendix A has been added as a reference summary of helpful material on sets, logical statements, induction, counting arguments, binomial coefficients, relations, and the pigeonhole principle. Many proofs have been reworded in more patient language with additional details, and more examples have been added. More than 350 exercises have been added, mostly easier exercises in Chapters 17. There are now more than 1200 exercises. More than 100 illustrations have been added; there are now more than 400. In illustrations showing several types of edges, the switch to bold and solid edges instead of solid and dashed edges has increased clarity. Easier.problems are now grouped at the beginning of each exercise section, usable as warmups. Statements of some exercises have been clarified. In addition to hints accompanying the exercise statements, there is now an appendix of supplemental hints. For easier access, terms being defined are in bold type, and the vast majority of them appear in Definition items. For easier access, the glossary of notation has been placed on the inside covers. Material involving Eulerian circuits, digraphs, and Turyn's Theorem has been relocated to facilitate more efficient learning. Chapters 6 and 7 have been switched to introduce the idea of planarity earlier, and the section on complexity has become an appendix. The glossary has been improved to eliminate errors and to emphasize items more directly related to the text. FeaturesVarious features of this book facilitate students' efforts to understand the material. There is discussion of proof techniques, more than 1200 exercises of varying difficulty, more than 400 illustrations, and many examples. Proofs are presented in full in the text.Many undergraduates begin a course in graph theory with little exposure to proof techniques.