# Book:Gary Chartrand/Introductory Graph Theory

## Gary Chartrand: *Introductory Graph Theory*

Published $1985$, **Dover Publications, Inc.**

- ISBN 0-486-24775-9.

### Subject Matter

Republication with corrections of *Graphs as Mathematical Models* from $1977$.

### Contents

- Preface

- Acknowledgements

- Chapter l: 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 Cohnector 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 the 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