Introduction Graphs The Degree of a Vertex Isomorphic Graphs Regular Graphs Bipartite Graphs Operations on Graphs Degree Sequences Multigraphs Exercises for Chapter 1 Connected Graphs and Distance Connected Graphs Distance in Graphs Exercises for Chapter 2 Trees Nonseparable Graphs Introduction to Trees Spanning Trees The Minimum Spanning Tree Problem Exercises for Chapter 3 Connectivity Connectivity and Edge-Connectivity Theorems of Menger and Whitney Exercises for Chapter 4 Eulerian Graphs The Königsberg Bridge Problem Eulerian Circuits and Trails Exercises for Chapter 5 Hamiltonian Graphs Hamilton's Icosian Game Sufficient Conditions for Hamiltonicity Toughness of Graphs Highly Hamiltonian Graphs Powers of Graphs and Line Graphs Exercises for Chapter 6 Digraphs Introduction to Digraphs Strong Digraphs Eulerian and Hamiltonian Digraphs Tournaments Kings in Tournaments Hamiltonian Tournaments Exercises for Chapter 7 Flows in Networks Networks The Max-Flow Min-Cut Theorem Menger Theorems for Digraphs Exercises for Chapter 8 Automorphisms and Reconstruction The Automorphism Group of a Graph Cayley Color Graphs The Reconstruction Problem Exercises for Chapter 9 Planar Graphs The Euler Identity Maximal Planar Graphs Characterizations of Planar Graphs Hamiltonian Planar Graphs Exercises for Chapter 10 Nonplanar Graphs The Crossing Number of a Graph The Genus of a Graph The Graph Minor Theorem Exercises for Chapter 11 Matchings, Independence and Domination Matchings 1-Factors Independence and Covers Domination Exercises for Chapter 12 Factorization and Decomposition Factorization Decomposition Cycle Decomposition Graceful Graphs Exercises for Chapter 13 Vertex Colorings The Chromatic Number of a Graph Color-Critical Graphs Bounds for the Chromatic Number Exercises for Chapter 14 Perfect Graphs and List Colorings Perfect Graphs The Perfect and Strong Perfect Graph Theorems List Colorings Exercises for Chapter 15 Map Colorings The Four Color Problem Colorings of Planar Graphs List Colorings of Planar Graphs The Conjectures of Hajós and Hadwiger Chromatic Polynomials The Heawood Map-Coloring Problem Exercises for Chapter 16 Edge Colorings The Chromatic Index of a Graph Class One and Class Two Graphs Tait Colorings Exercises for Chapter 17 Nowhere-Zero Flows, List Edge Colorings Nowhere-Zero Flows List Edge Colorings Total Colorings Exercises for Chapter 18 Extremal Graph Theory Turán's Theorem Extremal Subgraphs Cages Exercises for Chapter 19 Ramsey Theory Classical Ramsey Numbers More General Ramsey Numbers Exercises for Chapter 20 The Probabilistic Method The Probabilistic Method Random Graphs Exercises for Chapter 21 Hints and Solutions to Odd-Numbered Exercises Bibliography Supplemental References Index of Names Index of Mathematical Terms List of Symbols.