Graph Theory

I Fundamentals.- 1. Definitions.- 2. Paths, Cycles and Trees.- 3. Hamilton Cycles and Euler Circuits.- 4. Planar Graphs.- 5. An Application of Euler Trails to Algebra.- Exercises.- Notes.- II Electrical Networks.- 1. Graphs and Electrical Networks.- 2. Squaring the Square.- 3. Vector Spaces and Matrices Associated with Graphs.- Exercises.- Notes.- III Flows, Connectivity and Matching.- 1. Flows in Directed Graphs.- 2. Connectivity and Menger’s Theorem.- 3. Matching.- 4. Tutte’s 1-Factor Theorem.- Exercises.- Notes.- IV Extremal Problems.- 1. Paths and Cycles.- 2. Complete Subgraphs.- 3. Hamilton Paths and Cycles.- 4. The Structure of Graphs.- Exercises.- Notes.- V Colouring.- 1. Vertex Colouring.- 2. Edge Colouring.- 3. Graphs on Surfaces.- Exercises.- Notes.- VI Ramsey Theory.- 1. The Fundamental Ramsey Theorems.- 2. Monochromatic Subgraphs.- 3. Ramsey Theorems in Algebra and Geometry.- 4. Subsequences.- Exercises.- Notes.- VII Random Graphs.- 1. Complete Subgraphs and Ramsey Numbers—The Use of the Expectation.- 2. Girth and Chromatic Number—Altering a Random Graph.- 3. Simple Properties of Almost All Graphs—The Basic Use of Probability.- 4. Almost Determined Variables—The Use of the Variance.- 5. Hamilton Cycles—The Use of Graph Theoretic Tools.- Exercises.- Notes.- VIII Graphs and Groups.- 1. Cayley and Schreier Diagrams.- 2. Applications of the Adjacency Matrix.- 3. Enumeration and Pólya’s Theorem.- Exercises.- Notes.- Index of Symbols.