Content: IntroductionGraphsThe Degree of a VertexIsomorphic GraphsRegular GraphsBipartite GraphsOperations on GraphsDegree SequencesMultigraphsExercises for Chapter 1Connected Graphs and DistanceConnected GraphsDistance in GraphsExercises for Chapter 2TreesNonseparable GraphsIntroduction to TreesSpanning TreesThe Minimum Spanning Tree ProblemExercises for Chapter 3ConnectivityConnectivity and Edge-ConnectivityTheorems of Menger and WhitneyExercises for Chapter 4Eulerian GraphsThe Konigsberg Bridge ProblemEulerian Circuits and TrailsExercises for Chapter 5Hamiltonian GraphsHamilton's Icosian GameSufficient Conditions for HamiltonicityToughness of GraphsHighly Hamiltonian GraphsPowers of Graphs and Line GraphsExercises for Chapter 6DigraphsIntroduction to DigraphsStrong DigraphsEulerian and Hamiltonian DigraphsTournamentsKings in TournamentsHamiltonian TournamentsExercises for Chapter 7Flows in NetworksNetworksThe Max-Flow Min-Cut TheoremMenger Theorems for DigraphsExercises for Chapter 8Automorphisms and ReconstructionThe Automorphism Group of a GraphCayley Color GraphsThe Reconstruction ProblemExercises for Chapter 9Planar GraphsThe Euler IdentityMaximal Planar GraphsCharacterizations of Planar GraphsHamiltonian Planar GraphsExercises for Chapter 10Nonplanar GraphsThe Crossing Number of a GraphThe Genus of a GraphThe Graph Minor TheoremExercises for Chapter 11Matchings, Independence and DominationMatchings1-FactorsIndependence and CoversDominationExercises for Chapter 12Factorization and DecompositionFactorizationDecompositionCycle DecompositionGraceful GraphsExercises for Chapter 13Vertex ColoringsThe Chromatic Number of a GraphColor-Critical GraphsBounds for the Chromatic NumberExercises for Chapter 14Perfect Graphs and List ColoringsPerfect GraphsThe Perfect and Strong Perfect Graph TheoremsList ColoringsExercises for Chapter 15Map ColoringsThe Four Color ProblemColorings of Planar GraphsList Colorings of Planar GraphsThe Conjectures of Hajos and HadwigerChromatic PolynomialsThe Heawood Map-Coloring ProblemExercises for Chapter 16Edge ColoringsThe Chromatic Index of a GraphClass One and Class Two GraphsTait ColoringsExercises for Chapter 17Nowhere-Zero Flows, List Edge ColoringsNowhere-Zero FlowsList Edge ColoringsTotal ColoringsExercises for Chapter 18Extremal Graph TheoryTuran's TheoremExtremal SubgraphsCagesExercises for Chapter 19Ramsey TheoryClassical Ramsey NumbersMore General Ramsey NumbersExercises for Chapter 20The Probabilistic MethodThe Probabilistic MethodRandom GraphsExercises for Chapter 21Hints and Solutions to Odd-Numbered ExercisesBibliographySupplemental ReferencesIndex of NamesIndex of Mathematical TermsList of Symbols