Graphs & Digraphs: 6th Edition (Hardback) book cover

Graphs & Digraphs

6th Edition

By Gary Chartrand, Linda Lesniak, Ping Zhang

Chapman and Hall/CRC

640 pages | 343 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781498735766
pub: 2015-12-22
SAVE ~$24.00
eBook (VitalSource) : 9780429155222
pub: 2015-12-16
from $60.00

FREE Standard Shipping!


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.


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

Table of Contents



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

About the Authors

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.

About the Series

Textbooks in Mathematics

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COMPUTERS / Operating Systems / General
MATHEMATICS / Combinatorics