You are here

Introductory Graph Theory

Gary Chartrand
Publisher: 
Dover Publications
Publication Date: 
1984
Number of Pages: 
320
Format: 
Paperback
Price: 
16.95
ISBN: 
9780486247755
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Allen Stenger
, on
10/1/2015
]

This is a fun but comprehensive introduction to graph theory. It has few prerequisites and is aimed at lower-division undergraduates, but would also be suitable for self-study by bright high schoolers. This is a 1985 Dover corrected and retitled reprint of the 1977 Prindle Weber & Schmidt work Graphs as Mathematical Models.

The book’s best feature is that each topic is introduced by a concrete example problem (sometimes real, sometimes contrived). The book develops a graph as a model of the problem and then solves the graph problem (usually by developing and applying a general theorem, although sometimes by ad hoc methods). In tone the book reminds me a lot of J. D. Williams’s The Compleat Strategyst: Being a Primer on the Theory of Games of Strategy, even though the present book is aimed at math students, covers a much wider range, and does contain proofs (but is organized so that these can be skipped).

The exercises are quite varied and suitably difficult, with a mixture of proofs, examples, and further concrete problems. Solutions and hints to some problems are in the back of the book.

The book has aged well. The graph theory facts covered here are still the central ones today. A few of the examples were too topical: for example there are discussions of the game Instant Insanity and of Transactional Analysis, both of which were popular in the 1970s when the book was written but have faded from the public consciousness today.

About thirty years later Chartrand (with Ping Zhang) wrote another introductory graph theory text, published in 2005 as Introduction to Graph Theory and reprinted in revised from in 2012 as A First Course in Graph Theory. The newer book covers the same topics as the present book, although in more depth. It is a more conventional text and is oriented to definitions and theorems rather than to concrete problems, so it has more of a pure-math feel. It has a number of Excursion sections at the ends of chapters, many of which treat the same concrete problems covered in the present book.

Yet another introductory book by the same authors (plus Art Benjamin) appeared in 2015: The Fascinating World of Graph Theory. This lies somewhere between the two earlier books: it’s still a fairly conventional text, with a smoother narrative, but includes a lot of motivating examples and is closer to being an applied book.

Bottom line: still valuable, even though the author has done two more takes on the same subject matter since it appeared.


Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.

 

Chapter 1 Mathematical Models
  1.1 Nonmathematical Models
  1.2 Mathematical Models
  1.3 Graphs
  1.4 Graphs as Mathematical Models
  1.5 Directed Graphs as Mathematical Models
  1.6 Networks as Mathematical Models
  Chapter 2 Elementary Concepts of Graph Theory
  2.1 The Degree of a Vertex
  2.2 Isomorphic Graphs
  2.3 Connected Graphs
  2.4 Cut-Vertices and Bridges
  Chapter 3 Transportation Problems
  3.1 The Königsberg Bridge Problem: An Introduction to Eulerian Graphs
  3.2 The Salesman's Problem: An Introduction to Hamiltonian Graphs
  Chapter 4 Connection Problems
  4.1 The Minimal Connector Problem: An Introduction to Trees
  *4.2 Trees and Probability
  4.3 PERT and the Critical Path Method
  Chapter 5 Party Problems
  5.1 The Problem of Eccentric Hosts: An Introduction to Ramsey Numbers
  5.2 The Dancing Problem: An Introduction to Matching
  Chapter 6 Games and Puzzles
  6.1 "The Problem of the Four Multicolored Cubes: A Solution to "Instant Insanity"
  6.2 The Knight's Tour
  6.3 The Tower of Hanoi
  6.4 The Three Cannibals and Three Missionaries Problem
  Chapter 7 Digraphs and Mathematical Models
  7.1 A Traffic System Problem: An Introduction to Orientable Graphs
  7.2 Tournaments
  7.3 Paired Comparisons and How to Fix Elections
  Chapter 8 Graphs and Social Psychology
  8.1 The Problem of Balance
  8.2 The Problem of Clustering
  8.3 Graphs and Transactional Analysis
  Chapter 9 Planar Graphs and Coloring Problems
  9.1 The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs
  9.2 A Scheduling Problem: An Introduction to Chromatic Numbers
  9.3 The Four Color Problem
  *Chapter 10 Graphs and Other Mathematics
  10.1 Graphs and Matrices
  10.2 Graphs and Topology
  10.3 Graphs and Groups
  "Appendix Sets, Relations, Functions, Proofs"
  A.1 Sets and Subsets
  A.2 Cartesian Products and Relations
  A.3 Equivalence Relations
  A.4 Functions
  A.5 Theorems and Proofs
  A.6 Mathematical Induction
  "Answers, Hints, and Solutions to Selected Exercises"
  Index