Prelude xi
Part One Graph Theory 1
Chapter 1 Elements of Graph Theory 3
1.1 Graph Models 3
1.2 Isomorphism 14
1.3 Edge Counting 24
1.4 Planar Graphs 31
1.5 Summary and References 44
Supplementary Exercises 45
Chapter 2 Covering Circuits and Graph Coloring 49
2.1 Euler Cycles 49
2.2 Hamilton Circuits 56
2.3 Graph Coloring 68
2.4 Coloring Theorems 77
2.5 Summary and References 86
Supplement: Graph Model for Instant Insanity 87
Supplement Exercises 92
Chapter 3 Trees and Searching 93
3.1 Properties of Trees 93
3.2 Search Trees and Spanning Trees 103
3.3 The Traveling Salesperson Problem 113
3.4 Tree Analysis of Sorting Algorithms 121
3.5 Summary and References 125
Chapter 4 Network Algorithms 127
4.1 Shortest Paths 127
4.2 Minimum Spanning Trees 131
4.3 Network Flows 135
4.4 Algorithmic Matching 153
4.5 The Transportation Problem 164
4.6 Summary and References 174
Part Two Enumeration 177
Chapter 5 General Counting Methods for Arrangements and Selections 179
5.1 Two Basic Counting Principles 179
5.2 Simple Arrangements and Selections 189
5.3 Arrangements and Selections with Repetitions 206
5.4 Distributions 214
5.5 Binomial Identities 226
5.6 Summary and References 236
Supplement: Selected Solutions to Problems in Chapter 5 237
Chapter 6 Generating Functions 249
6.1 Generating Function Models 249
6.2 Calculating Coefficients of Generating Functions 256
6.3 Partitions 266
6.4 Exponential Generating Functions 271
6.5 A Summation Method 277
6.6 Summary and References 281
Chapter 7 Recurrence Relations 283
7.1 Recurrence Relation Models 283
7.2 Divide-and-Conquer Relations 296
7.3 Solution of Linear Recurrence Relations 300
7.4 Solution of Inhomogeneous Recurrence Relations 304
7.5 Solutions with Generating Functions 308
7.6 Summary and References 316
Chapter 8 Inclusion–Exclusion 319
8.1 Counting with Venn Diagrams 319
8.2 Inclusion–Exclusion Formula 328
8.3 Restricted Positions and Rook Polynomials 340
8.4 Summary and Reference 351
Part Three Additional Topics 353
Chapter 9 Polya’s Enumeration Formula 355
9.1 Equivalence and Symmetry Groups 355
9.2 Burnside’s Theorem 363
9.3 The Cycle Index 369
9.4 Polya’s Formula 375
9.5 Summary and References 382
Chapter 10 Games with Graphs 385
10.1 Progressively Finite Games 385
10.2 Nim-Type Games 393
10.3 Summary and References 400
Postlude 401
Appendix 415
A.1 Set Theory 415
A.2 Mathematical Induction 420
A.3 A Little Probability 423
A.4 The Pigeonhole Principle 427
A.5 Computational Complexity and NP-Completeness 430
Glossary of Counting and Graph Theory Terms 435
Bibliography 439
Solutions To Odd-Numbered Problems 441
Index 475
