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. Language: English