You are here

Home » MAA Publications » MAA Reviews » Introduction to Graph Theory

Introduction to Graph Theory

Gary Chartrand and Ping Zhang
Publisher: 
McGraw-Hill
Publication Date: 
2005
Number of Pages: 
449
Format: 
Hardcover
Series: 
The Walter Rudin Student Series in Advanced Mathematics
Price: 
104.69
ISBN: 
0073204161
Category: 
Textbook
BLL Rating: 
BLL*

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Donald L. Vestal
, on
04/8/2006
]

To honor Walter Rudin's contributions to mathematics education, McGraw-Hill has created the Walter Rudin Student Series in Advanced Mathematics. Chartrand and Zhang's Introduction to Graph Theory is one of the first books in this series. Being part of this series (or, for that matter, any series invoking Rudin's name) sets up rather high expectations. To the authors' credit, this book meets these expectations.

The authors' goals are to introduce undergraduates to the discipline of graph theory, informing them of the subject — as well as the people who shaped it — and then showing some of its applications. The text is very well written, accessible to undergraduate, and perhaps even some high school, students (provided they can keep track of the many terms that are used). The authors make good use of pictures and diagrams. They also adopt what is increasingly becoming a common practice: labeling proof techniques. Thus after the term Proof we see something like [direct proof] or [proof by contradiction] or [proof by minimum counterexample].

The lives of some of the people who have played major roles in the development of graph theory are discussed throughout the text. These are often done within a section. Personally, I prefer these diversions to either be boxed off to the side or in their own section. Placing them within a section makes it feel like a distraction. (The diversions are interesting, to be sure — just distracting.)

The topics covered in the book are isomorphic graphs, trees, connectivity and Menger's Theorem, Eulerian and Hamiltonian graphs, digraphs, graph factorization, planarity, graph coloring, Ramsey numbers, the notion of distance in a graph, and domination numbers. Each section contains several exercises, many along the lines of "construct a graph with the following properties…" And each chapter ends with a section or two of excursions and/or explorations, in which the students get to see some of the applications of the theory from the chapter. In addition to all of this, there are three appendices which review the notion of logic and proofs, a section with solutions and hints for odd-numbered problems, twelve pages of references, an index of names, an index of mathematical terms, and a list of symbols. This is probably just about as ideal a text as one could have in an introductory course on graph theory. And, as a whole, this book makes for a fine entry in the Walter Rudin Student Series in Advanced Mathematics.

Donald L. Vestal is Associate Professor of Mathematics at Missouri Western State University. His interests include number theory, combinatorics, and a deep admiration for the crime-fighting efforts of the Aqua Teen Hunger Force. He can be reached at vestal@missoriwestern.edu

 

1 Introduction

1.1 Graphs and Graph Models

1.2 Connected Graphs

1.3 Common Classes of Graphs

1.4 Multigraphs and Digraphs

2 Degrees

2.1 The Degree of a Vertex

2.2 Regular Graphs

2.3 Degree Sequences

2.4 Excursion: Graphs and Matrices

2.5 Exploration: Irregular Graphs

3 Isomorphic Graphs

3.1 The Definition of Isomorphism

3.2 Isomorphism as a Relation

3.3 Excursion: Graphs and Groups

3.4 Excursion: Reconstruction and Solvability

4 Trees

4.1 Bridges

4.2 Trees

4.3 The Minimum Spanning Tree Problem

4.4 Excursion: The Number of Spanning Trees

5 Connectivity

5.1 Cut-Vertices

5.2 Blocks

5.3 Connectivity

5.4 Menger's Theorem

5.5 Exploration: Geodetic Sets

6 Traversability

6.1 Eulerian Graphs

6.2 Hamiltonian Graphs

6.3 Exploration: Hamiltonian Walks and Numbers

6.4 Excursion: The Early Books of Graph Theory

7 Digraphs

7.1 Strong Digraphs

7.2 Tournaments

7.3 Excursion: Decision-Making

7.4 Exploration: Wine Bottle Problems

8 Matchings and Factorization

8.1 Matchings

8.2 Factorization

8.3 Decompositions and Graceful Labelings

8.4 Excursion: Instant Insanity

8.5 Excursion: The Petersen Graph

8.6 Exploration: -Labeling of Graphs

9 Planarity

9.1 Planar Graphs

9.2 Embedding Graphs on Surfaces

9.3 Excursion: Graph Minors

9.4 Exploration: Embedding Graphs in Graphs

10 Coloring

10.1 The Four Color Problem

10.2 Vertex Coloring

10.3 Edge Coloring

10.4 Excursion: The Heawood Map Coloring Theorem

10.5 Exploration: Local Coloring

11 Ramsey Numbers

11.1 The Ramsey Number of Graphs

11.2 Turan's Theorem

11.3 Exploration: Rainbow Ramsey Numbers

11.4 Excursion: Erdös Numbers

12 Distance

12.1 The Center of a Graph

12.2 Distant Vertices

12.3 Excursion: Locating Numbers

12.4 Excursion: Detour and Directed Distance

12.5 Exploration: Channel Assignment

12.6 Exploration: Distance Between Graphs

13 Domination

13.1 The Domination Number of a Graph

13.2 Exploration: Stratification

13.3 Exploration: Lights Out

13.4 Excursion: And Still It Grows More Colorful

Appendix 1 Sets and Logic
Appendix 2 Equivalence Relations and Functions
Appendix 3 Methods of Proof
Tags: 
Graph Theory