**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.

**Introduction**Graphs

The Degree of a Vertex

Isomorphic Graphs

Regular Graphs

Bipartite Graphs

Operations on Graphs

Degree Sequences

Multigraphs

Exercises for Chapter 1

**Connected Graphs and Distance**Connected Graphs

Distance in Graphs

Exercises for Chapter 2

**Trees**Nonseparable Graphs

Introduction to Trees

Spanning Trees

The Minimum Spanning Tree Problem

Exercises for Chapter 3

**Connectivity**

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

**Digraphs**Introduction to Digraphs

Strong Digraphs

Eulerian and Hamiltonian Digraphs

Tournaments

Kings in Tournaments

Hamiltonian Tournaments

Exercises for Chapter 7

**Flows in Networks**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**Matchings

1-Factors

Independence and Covers

Domination

Exercises for Chapter 12

**Factorization and Decomposition**Factorization

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**

Cages

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

Bibliography

Supplemental References

Index of Names

Index of Mathematical Terms

List of Symbols

### Biography

**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 MATH1211