Textbook in PDF format

This comprehensive text offers undergraduates a remarkably student-friendly introduction to graph theory. Written by two of the field's most prominent experts, it takes an engaging approach that emphasizes graph theory's history. Unique examples and lucid proofs provide a sound yet accessible treatment that stimulates interest in an evolving subject and its many applications. Optional sections designated as "excursion" and "exploration" present interesting sidelights of graph theory and touch upon topics that allow students the opportunity to experiment and use their imaginations. Three appendixes review important facts about sets and logic, equivalence relations and functions, and the methods of proof. The text concludes with solutions or hints for odd-numbered exercises, in addition to references, indexes, and a list of symbols. Introduction Graphs and Graph Models Connected Graphs Common Classes of Graphs Multigraphs and Digraphs Degrees The Degree of a Vertex Regular Graphs Degree Sequences Excursion: Graphs and Matrices Exploration: Irregular Graphs Isomorphic Graphs The Definition of Isomorphism Isomorphism as a Relation Excursion: Graphs and Groups Excursion: Reconstruction and Solvability Trees Bridges Trees The Minimum Spanning Tree Problem Excursion: The Number of Spanning Trees Connectivity Cut-Vertices Blocks Connectivity Menger’s Theorem Exploration: Powers and Edge Labelings Traversability Eulerian Graphs Hamiltonian Graphs Exploration: Hamiltonian Walks Excursion: Early Books of Graph Theory Digraphs Strong Digraphs Tournaments Excursion: Decision-Making Exploration: Wine Bottle Problems Matchings and Factorization Matchings Factorization Decompositions and Graceful Labelings Excursion: Instant Insanity Excursion: ‘The Petersen Graph Exploration: Bi-Graceful Graphs Planarity Planar Graphs Embedding Graphs on Surfaces Excursion: Graph Minors Exploration: Embedding Graphs in Graphs Coloring Graphs The Four Color Problem Vertex Coloring Edge Coloring Excursion: The Heawood Map Coloring Theorem Exploration: Modular Coloring Ramsey Numbers The Ramsey Number of Graphs Turan’s Theorem Exploration: Modified Ramsey Numbers Excursion: Erdos Numbers Distance The Center of a Graph Distant Vertices Excursion: Locating Numbers Excursion: Detour and Directed Distance Exploration: Channel Assignment Exploration: Distance Between Graphs Domination The Domination Number of a Graph Exploration: Stratification Exploration: Lights Out Excursion: And Still It Grows More Colorful Appendices Sets and Logic Equivalence Relations and Functions Methods of Proof Solutions and Hints for Odd-Numbered Exercises References Index of Names Index of Mathematical Terms List of Symbols