Graphs & Digraphs, Fifth Edition

Free Standard Shipping

Purchasing Options

ISBN 9781439826270
Cat# K11263



SAVE 20%

eBook (VitalSource)
ISBN 9781439826294
Cat# KE11180



SAVE 30%

eBook Rentals


  • Details the concepts, theorems, and applications of graph theory
  • Elucidates the concepts and theory with clear proofs and abundant examples
  • Discusses the contributions of many historical figures to graph theory
  • Includes numerous exercises at the end of each section
  • Presents hints and solutions to odd-numbered exercises

Solutions manual available for qualifying instructors


Continuing to provide a carefully written, thorough introduction, Graphs & Digraphs, Fifth Edition expertly describes the concepts, theorems, history, and applications of graph theory. Nearly 50 percent longer than its bestselling predecessor, this edition reorganizes the material and presents many new topics.

New to the Fifth Edition

  • New or expanded coverage of graph minors, perfect graphs, chromatic polynomials, nowhere-zero flows, flows in networks, degree sequences, toughness, list colorings, and list edge colorings
  • New examples, figures, and applications to illustrate concepts and theorems
  • Expanded historical discussions of well-known mathematicians and problems
  • More than 300 new exercises, along with hints and solutions to odd-numbered exercises at the back of the book
  • Reorganization of sections into subsections to make the material easier to read
  • Bolded definitions of terms, making them easier to locate

Despite a field that has evolved over the years, this student-friendly, classroom-tested text remains the consummate introduction to graph theory. It explores the subject’s fascinating history and presents a host of interesting problems and diverse applications.

Table of Contents

Introduction to Graphs
Graphs and Subgraphs
Degree Sequences
Connected Graphs and Distance
Multigraphs and Digraphs

Trees and Connectivity
Nonseparable Graphs
Spanning Trees
Connectivity and Edge-Connectivity
Menger’s Theorem

Eulerian and Hamiltonian Graphs
Eulerian Graphs
Hamiltonian Graphs
Powers of Graphs and Line Graphs

Strong Digraphs
Flows in Networks

Graphs: History and Symmetry
Some Historical Figures of Graph Theory
The Automorphism Group of a Graph
Cayley Color Graphs
The Reconstruction Problem

Planar Graphs
The Euler Identity
Planarity versus Nonplanarity
The Crossing Number of a Graph
Hamiltonian Planar Graphs

Graph Embeddings
The Genus of a Graph
2-Cell Embeddings of Graphs
The Maximum Genus of a Graph
The Graph Minor Theorem

Vertex Colorings
The Chromatic Number of a Graph
Color-Critical Graphs
Bounds for the Chromatic Number
Perfect Graphs
List Colorings

Map Colorings
The Four Color Problem
Colorings of Planar Graphs
The Conjectures of Hajós and Hadwiger
Chromatic Polynomials
The Heawood Map-Coloring Problem

Matchings, Factorization, and Domination
Matchings and Independence in Graphs
Decomposition and Graceful Graphs

Edge Colorings
Chromatic Index and Vizing’s Theorem
Class One and Class Two Graphs
Tait Colorings
Nowhere-Zero Flows
List Edge Colorings and Total Colorings

Extremal Graph Theory
Turán’s Theorem
Ramsey Theory

Hints and Solutions to Odd-Numbered Exercises
Index of Names
Index of Mathematical Terms
List of Symbols

Author Bio(s)

Gary Chartrand is a professor emeritus of mathematics at Western Michigan University. Linda Lesniak is a professor emeritus of mathematics at Drew University. Ping Zhang is a professor of mathematics at Western Michigan University. All three have authored or co-authored many textbooks in mathematics and numerous research articles in graph theory.

Editorial Reviews

Gary Chartrand has influenced the world of Graph Theory for almost half a century. He has supervised more than a score of Ph.D. dissertations and written several books on the subject. The most widely known of these texts, Graphs and Digraphs, … has much to recommend it, with clear exposition, and numerous challenging examples [that] make it an ideal textbook for the advanced undergraduate or beginning graduate course. The authors have updated their notation to reflect the current practice in this still-growing area of study. By the authors’ estimation, the 5th edition is approximately 50% longer than the 4th edition. … the legendary Frank Harary, author of the second graph theory text ever produced, is one of the figures profiled. His book was the standard in the discipline for several decades. Chartrand, Lesniak and Zhang have produced a worthy successor.
—John T. Saccoman, MAA Reviews, June 2012 (This book is in the MAA's basic library list.)

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

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

Praise for the Fourth Edition:
… a popular point of entry to the field … has evolved with the field from a purely mathematical treatment to one that also addresses the needs of computer scientists.
L’Enseignement Mathématique

… emphasizes clear exposition, well-written proofs, and many original and innovative exercises of varying difficulty and challenge … For 25 years, Graphs & Digraphs, in its various editions, has served as an exemplary introduction to the emerging mathematical disciplines of graph theories, for advanced undergraduate and graduate students. It has also served established graph theorists, combinatorialists, and other discrete mathematicians, as well as computer scientists and chemists, as a useful reference work. The fourth edition continues these fine traditions.
Zentralblatt MATH