Graph Theory

This book is a concise - yet most carefully written - introduction to modern graph theory, covering all its major recent developments. It can be used both as a reliable textbook for an introductory course and as a graduate text: on each topic it covers all the basic material in full detail, and adds one or two deeper results (again with detailed proofs) to illustrate the more advanced methods of that field. This second edition extends the first in two ways. It offers a thoroughly revised and updated chapter on graph minors, which now includes full new proofs of two of the central Robertson-Seymour theorems (as well as a detailed sketch of the entire proof of their celebrated Graph Minor Theorem). Secondly, there is now a section of hints for all the exercises, to enhance their value for both individual study and classroom use. TOC: The Basics.- Matching.- Connectivity.- Planar Graphs.- Colouring.- Flows.- Substructures in Dense Graphs.- Ramsey Theory for Graphs.- Hamilton Cycles.- Random Graphs.- Minors, Trees, and WQO