Table of Contents

I Fundamentals.- I.1 Definitions.- I.2 Paths, Cycles, and Trees.- I.3 Hamilton Cycles and Euler Circuits.- I.4 Planar Graphs.- I.5 An Application of Euler Trails to Algebra.- I.6 Exercises.- II Electrical Networks.- II.1 Graphs and Electrical Networks.- II.2 Squaring the Square.- II.3 Vector Spaces and Matrices Associated with Graphs.- II.4 Exercises.- II.5 Notes.- III Flows, Connectivity and Matching.- III.1 Flows in Directed Graphs.- III.2 Connectivity and Menger’s Theorem.- III.3 Matching.- III.4 Tutte’s 1-Factor Theorem.- III.5 Stable Matchings.- III.6 Exercises.- III.7 Notes.- IV Extremal Problems.- IV.1 Paths and Cycles.- IV.2 Complete Subgraphs.- IV.3 Hamilton Paths and Cycles.- W.4 The Structure of Graphs.- IV 5 Szemerédi’s Regularity Lemma.- IV 6 Simple Applications of Szemerédi’s Lemma.- IV.7 Exercises.- IV.8 Notes.- V Colouring.- V.1 Vertex Colouring.- V.2 Edge Colouring.- V.3 Graphs on Surfaces.- V.4 List Colouring.- V.5 Perfect Graphs.- V.6 Exercises.- V.7 Notes.- VI Ramsey Theory.- VI.1 The Fundamental Ramsey Theorems.- VI.2 Canonical Ramsey Theorems.- VI.3 Ramsey Theory For Graphs.- VI.4 Ramsey Theory for Integers.- VI.5 Subsequences.- VI.6 Exercises.- VI.7 Notes.- VII Random Graphs.- VII.1 The Basic Models-The Use of the Expectation.- VII.2 Simple Properties of Almost All Graphs.- VII.3 Almost Determined Variables-The Use of the Variance.- VII.4 Hamilton Cycles-The Use of Graph Theoretic Tools.- VII.5 The Phase Transition.- VII.6 Exercises.- VII.7 Notes.- VIII Graphs, Groups and Matrices.- VIII.1 Cayley and Schreier Diagrams.- VIII.2 The Adjacency Matrix and the Laplacian.- VIII.3 Strongly Regular Graphs.- VIII.4 Enumeration and Pólya’s Theorem.- VIII.5 Exercises.- IX Random Walks on Graphs.- IX.1 Electrical Networks Revisited.- IX.2 Electrical Networks and Random Walks.- IX.3 Hitting Times and Commute Times.- IX.4 Conductance and Rapid Mixing.- IX.5 Exercises.- IX.6 Notes.- X The Tutte Polynomial.- X.1 Basic Properties of the Tutte Polynomial.- X.2The Universal Form of the Tutte Polynomial.- X.3 The Tutte Polynomial in Statistical Mechanics.- X.4 Special Values of the Tutte Polynomial.- X.5 A Spanning Tree Expansion of the Tutte Polynomial.- X.6 Polynomials of Knots and Links.- X.7 Exercises.- X.8 Notes.- Symbol Index.- Name Index.

Promotional Information

Springer Book Archives

Reviews

"...This book is likely to become a classic, and it deserves to be on the shelf of everyone working in graph theory or even remotely related areas, from graduate student to active researcher."--MATHEMATICAL REVIEWS