640 Pages 343 B/W Illustrations
    by Chapman & Hall

    Graphs & Digraphs masterfully employs student-friendly exposition, clear proofs, abundant examples, and numerous exercises to provide an essential understanding of the concepts, theorems, history, and applications of graph theory.

    Fully updated and thoughtfully reorganized to make reading and locating material easier for instructors and students, the Sixth Edition of this bestselling, classroom-tested text:

    • Adds more than 160 new exercises
    • Presents many new concepts, theorems, and examples
    • Includes recent major contributions to long-standing conjectures such as the Hamiltonian Factorization Conjecture, 1-Factorization Conjecture, and Alspach’s Conjecture on graph decompositions
    • Supplies a proof of the perfect graph theorem
    • Features a revised chapter on the probabilistic method in graph theory with many results integrated throughout the text

    At the end of the book are indices and lists of mathematicians’ names, terms, symbols, and useful references. There is also a section giving hints and solutions to all odd-numbered exercises. A complete solutions manual is available with qualifying course adoption.

    Graphs & Digraphs, Sixth Edition remains the consummate text for an advanced undergraduate level or introductory graduate level course or two-semester sequence on graph theory, exploring the subject’s fascinating history while covering a host of interesting problems and diverse applications.

    The Degree of a Vertex
    Isomorphic Graphs
    Regular Graphs
    Bipartite Graphs
    Operations on Graphs
    Degree Sequences
    Exercises for Chapter 1

    Connected Graphs and Distance
    Connected Graphs
    Distance in Graphs
    Exercises for Chapter 2

    Nonseparable Graphs
    Introduction to Trees
    Spanning Trees
    The Minimum Spanning Tree Problem
    Exercises for Chapter 3

    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

    Introduction to Digraphs
    Strong Digraphs
    Eulerian and Hamiltonian Digraphs
    Kings in Tournaments
    Hamiltonian Tournaments
    Exercises for Chapter 7

    Flows in 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
    Independence and Covers
    Exercises for Chapter 12

    Factorization and 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
    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


    Supplemental References

    Index of Names

    Index of Mathematical Terms

    List of Symbols


    Gary Chartrand is a professor emeritus of mathematics at Western Michigan University, Kalamazoo, Michigan, USA. Linda Lesniak, a professor emeritus of mathematics from Drew University, Madison, New Jersey, USA, is currently a visiting mathematician at Western Michigan University, Kalamazoo, Michigan, USA. Ping Zhang is a professor of mathematics at Western Michigan University, Kalamazoo, Michigan, USA. All three have authored or coauthored many textbooks in mathematics and numerous research articles in graph theory.

    Praise for the Previous Edition

    "Now in its fifth edition, its success as a textbook is indicative of its quality and its clarity of presentation. … The authors also describe the fascinating history behind some of the key problems in graph theory and, to a lesser extent, their applications. This book describes the key concepts you need to get started in graph theory. … It provides all you might need to know about graph embeddings and graph colorings. Moreover, it analyzes many other topics that more general discrete mathematics monographs do not always cover, such as network flows, minimum cuts, matchings, factorization, decomposition, and even extremal graph theory. … This thorough textbook includes hundreds of exercises at the end of each section. Hints and solutions for odd-numbered exercises are included in the appendix, making it especially suitable for self-learning."
    —Fernando Berzal, Computing Reviews, September 2011

    "As with the earlier editions, the current text emphasizes clear exposition, well-written proofs, and many original and innovative exercises of varying difficulty and challenge. … The fifth edition continues and extends these fine traditions."
    —Arthur T. White, Zentralblatt MATH 1211