Textbook in PDF format

This standard textbook on modern graph theory combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject, with concise yet complete proofs, while offering glimpses of more advanced methods in each field via one or two deeper results. This is a major new edition. The book can be used as a reliable text for an introductory graduate course and is also suitable for self-study. About the sixth edition This sixth edition covers a major update on previously existing material, while also adding some new sections on topics that reflect the directions which graph theory has taken more recently. The largest addition of new material comes in Chapter 7, Extremal graph theory, where I have modernized the treatment of the regularity lemma by adding a section on ‘regularity tools’: the counting lemma, and the removal lemma. This is followed by a short new section on Szemeredi’s theorem. Its special case, Roth’s theorem, is proved there as an application of those regularity tools. The proof of the regularity lemma itself, and the introductory section on how it is typically applied, have been revised but essentially remained as before. There is an entirely new section on Hi-boundedness in Chapter 5. Gallai’s A-paths theorem now shows up explicitly in Chapter 3, as does Nash-Williams’s cycle-decomposition theorem in Chapter 8, a true classic in infinite graph theory. It is proved from Laviolette’s theorem, which is also newly included. Some classical theorems in the book have been furnished with shorter and more intuitive proofs, as these were recently discovered or brought to my attention. They include Lovasz’s perfect graph theorem in Chapter 5 and Seymour’s six-flow theorem in Chapter 6. For several others I streamlined the existing proofs, sometimes considerably, as I revisited them myself for teaching. These include Tutte’s flow polynomial theorem in Chapter 6, Turan’s theorem in Chapter 7, and the Erdos-Chavatal theorem in Chapter 10. Even the five colour theorem got a sweet and very short additional proof, which I had not previously known or thought of. Finally, the tree-of-tangles theorem in Chapter 12 has two even more powerful proofs now, neither of which existed when I wrote the section on tangles for the 5th. edition. However I have resisted including new proofs of classical results that are shorter but not more intuitive. The main reason for including any proofs at all remains to elucidate how graph theory typically works: with an emphasis on its diversity of methods, but also on single recurrent ideas which the reader may collect in their own personal toolkit. This is also the reason why, after many editions in which I included it, I have now omitted one of the two original proofs of the induced Ramsey theorem. The exposition now concentrates on the amalgamation proof, which turned out to be more fertile as Ramsey theory developed