Graph Theory: An Introduction to Proofs, Algorithms, and Applications

by Karin R Saoub

Overview

Graph Theory: An Introduction to Proofs, Algorithms, and Applications

Graph theory is the study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis.

This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations.

Current applications and exploratory exercises are provided to further the reader’s mathematical reasoning and understanding of the relevance of graph theory to the modern world.

Features

The first chapter introduces graph terminology, mathematical modeling using graphs, and a review of proof techniques featured throughout the book

• The second chapter investigates three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths.
• The third chapter focuses entirely on trees – terminology, applications, and theory.
• Four additional chapters focus around a major graph concept: connectivity, matching, coloring, and planarity. Each chapter brings in a modern application or approach.
• Hints and Solutions to selected exercises provided at the back of the book.

Author

Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She earned her PhD in mathematics from Arizona State University and BA from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.

Product Details

ISBN-13:	9780367743758
Publisher:	CRC Press
Publication date:	03/17/2021
Series:	Textbooks in Mathematics
Pages:	438
Product dimensions:	6.12(w) x 9.19(h) x (d)

About the Author

Dr. Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She received her PhD in Mathematics from Arizona State University and a Bachelor of Arts degree from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.

Table of Contents

Preface xi

1 Graph Models, Terminology, and Proofs 1

1.1 Tournaments 1

1.2 Introduction to Graph Models and Terminology 3

1.2.1 Digraphs 7

1.2.2 Weighted Graphs 9

1.2.3 Complete Graphs 11

1.2.4 Graph Complements 13

1.2.5 Bipartite Graphs 14

1.2.6 Graph Combinations 17

1.3 Isomorphisms 19

1.4 Matrix Representation 22

1.5 Proof Techniques 24

1.5.1 Direct Proofs 25

1.5.2 Indirect Proofs 26

1.5.3 Mathematical Induction 27

1.6 Degree Sequence 28

1.7 Tournaments Revisited 31

1.7.1 Score Sequence 31

1.7.2 Matrix Representation 38

1.8 Exercises 40

2 Graph Routes 45

2.1 Eulerian Circuits 45

2.1.1 Königsberg Bridge Problem 45

2.1.2 Touring a Graph 46

2.1.3 Eulerian Graphs 52

2.1.4 Algorithms 55

2.1.5 Applications 61

2.2 Hamiltonian Cycles 69

2.2.1 The Traveling Salesman Problem 81

2.2.2 Tournaments Revisited 97

2.3 Shortest Paths 101

2.3.1 Dijkstra's Algorithm 102

2.3.2 Walks Using Matrices 106

2.3.3 Distance, Diameter, and Radius 107

2.4 Exercises 114

3 Trees 123

3.1 Spanning Trees 124

3.1.1 Minimum Spanning Trees 125

3.2 Tree Properties 135

3.2.1 Tree Enumeration 139

3.3 Rooted Trees 143

3.3.1 Depth-First Search Tree 147

3.3.2 Breadth-First Search Tree 150

3.3.3 Mazes 152

3.4 Additional Applications 154

3.4.1 Traveling Salesman Revisited 154

3.4.2 Decision Trees 158

3.4.3 Chemical Graph Theory 160

3.5 Exercises 162

4 Connectivity and Flow 169

4.1 Connectivity Measures 169

4.1.1 k-Connected 170

4.1.2 k-Edge-Connected 171

4.1.3 Whitney's Theorem 172

4.2 Connectivity and Paths 175

4.2.1 Menger's Theorem 177

4.3 2-Connected Graphs 180

4.3.1 2-Edge-Connected 188

4.4 Network Flow 189

4.5 Centrality Measures 202

4.6 Exercises 207

5 Matching and Factors 213

5.1 Matching in Bipartite Graphs 216

5.1.1 Augmenting Paths and Vertex Covers 220

5.1.2 Hall's Theorem Revisited 234

5.2 Matching in General Graphs 237

5.2.1 Edmonds' Blossom Algorithm 244

5.2.2 Chinese Postman Problem 247

5.3 Stable Matching 249

5.3.1 Unacceptable Partners 255

5.3.2 Stable Roommates 258

5.4 Factors 260

5.5 Exercises 266

6 Graph Coloring 275

6.1 Four Color Theorem 275

6.2 Vertex Coloring 279

6.2.1 Coloring Strategies 284

6.2.2 General Results 289

6.3 Edge Coloring 295

6.3.1 1-Factorizations Revisited 302

6.3.2 Ramsey Numbers 306

6.4 Coloring Variations 309

6.4.1 On-line Coloring 309

6.4.2 Proof of Brooks' Theorem 323

6.4.3 Weighted Coloring 326

6.4.4 List Coloring 330

6.5 Exercises 332

7 Planarity 339

7.1 Kuratowski's Theorem 341

7.1.1 Euler's Formula 343

7.1.2 Cycle-Chord Method 349

7.1.3 Proof of Kuratowski's Theorem 351

7.2 Graph Coloring Revisited 355

7.3 Edge-Crossing 362

7.3.1 Thickness 366

7.4 Exercises 367

Appendix 373

A Set Theory 373

B Functions 377

C Matrix Operations 379

D Algorithm Efficiency 383

E Pseudocode 388

Selected Hints and Solutions 401

Bibliography 409

Image Credits 415

Index 417

Editorial Reviews

"This book is at a very nice level for an undergraduate course in graph theory. One of the really nice features are the inclusion of a quick introduction to proof techniques and the appendix which includes some other foundational knowledge students would need to complete some sections of the book. Including these prerequisite knowledge pieces in the book allows instructors to use this with minimal course prerequisites, which is a nice feature at small, undergraduate only institutions.

I also appreciate that the author highlights different ways to use this book: basics, application based, more theoretical. This allows the book to be used for a variety of courses. I appreciate the historical examples that appear in later sections (Eulerian graphs and planarity to name a few). I also like the emphasis on computation and modeling as this is a direction a lot of undergraduate curriculums are moving. The pseudocode at the end of the book is also really nice for departments (like my own) that are a joint mathematics and computer science department. This appendix allows instructors to potentially teach this class with more of a computer science focus as well.

I appreciate that the book seems to build in difficulty. The first few chapters seem pretty straight forward and basic, with little focus on proofs.

I also like that it is small and not as hefty as some of the other classic Graph Theory texts (like Doug West's book). It feels much more manageable to cover big portions of this in one semester. This would also be a great book for student self-study as it's friendly enough for students to read. The prose and multiple examples make it an easy read.

There are a good amount of exercises at the end of each section with both computational and theoretical options."
- Alison Marr, Southwestern University

From the Publisher