9780130144003

This book fills a need for a thorough introduction to graph theory that features both the understanding and writing of proofs about graphs. Verification that algorithms work is emphasized more than their complexity.An effective use of examples, and huge number of interesting exercises, demonstrate the topics of trees and distance, matchings and factors, connectivity and paths, graph coloring, edges and cycles, and planar graphs.For those who need to learn to make coherent arguments in the fields of mathematics and computer science.

Preface

xi

Fundamental Concepts

1

(66)

What Is a Graph?

1

(18)

The Definition

1

(2)

Graphs as Models

3

(3)

Matrices and Isomorphism

6

(5)

Decomposition and Special Graphs

11

(3)

Exercises

14

(5)

Paths, Cycles, and Trails

19

(15)

Connection in Graphs

20

(4)

Bipartite Graphs

24

(2)

Eulerian Circuits

26

(5)

Exercises

31

(3)

Vertex Degrees and Counting

34

(19)

Counting and Bijections

35

(3)

Extremal Problems

38

(6)

Graphic Sequences

44

(3)

Exercises

47

(6)

Directed Graphs

53

(14)

Definitions and Examples

53

(5)

Vertex Degrees

58

(2)

Eulerian Digraphs

60

(1)

Orientations and Tournaments

61

(2)

Exercises

63

(4)

Trees and Distance

67

(40)

Basic Properties

67

(14)

Properties of Trees

68

(2)

Distance in Trees and Graphs

70

(3)

Disjoint Spanning Trees (optional)

73

(2)

Exercises

75

(6)

Spanning Trees and Enumeration

81

(14)

Enumeration of Trees

81

(2)

Spanning Trees in Graphs

83

(4)

Decomposition and Graceful Labelings

87

(2)

Branchings and Eulerian Digraphs (optional)

89

(3)

Exercises

92

(3)

Optimization and Trees

95

(12)

Minimum Spanning Tree

95

(2)

Shortest Paths

97

(3)

Trees in Computer Science (optional)

100

(3)

Exercises

103

(4)

Matchings and Factors

107

(42)

Matchings and Covers

107

(16)

Maximum Matchings

108

(2)

Hall's Matching Condition

110

(2)

Min-Max Theorems

112

(1)

Independent Sets and Covers

113

(3)

Dominating Sets (optional)

116

(2)

Exercises

118

(5)

Algorithms and Applications

123

(13)

Maximum Bipartite Matching

123

(2)

Weighted Bipartite Matching

125

(5)

Stable Matchings (optional)

130

(2)

Faster Bipartite Matching (optional)

132

(2)

Exercises

134

(2)

Matchings in General Graphs

136

(13)

Tutte's 1-factor Theorem

136

(4)

f-factors of Graphs (optional)

140

(2)

Edmonds' Blossom Algorithm (optional)

142

(3)

Exercises

145

(4)

Connectivity and Paths

149

(42)

Cuts and Connectivity

149

(12)

Connectivity

149

(3)

Edge-connectivity

152

(3)

Blocks

155

(3)

Exercises

158

(3)

k-connected Graphs

161

(15)

2-connected Graphs

161

(3)

Connectivity of Digraphs

164

(2)

k-connected and k-edge-connected Graphs

166

(4)

Applications of Menger's Theorem

170

(2)

Exercises

172

(4)

Network Flow Problems

176

(15)

Maximum Network Flow

176

(5)

Integral Flows

181

(3)

Supplies and Demands (optional)

184

(4)

Exercises

188

(3)

Coloring of Graphs

191

(42)

Vertex Colorings and Upper Bounds

191

(13)

Definitions and Examples

191

(3)

Upper Bounds

194

(3)

Brooks' Theorem

197

(2)

Exercises

199

(5)

Structure of k-chromatic Graphs

204

(15)

Graphs with Large Chromatic Number

205

(2)

Extremal Problems and Turan's Theorem

207

(3)

Color-Critical Graphs

210

(2)

Forced Subdivisions

212

(2)

Exercises

214

(5)

Enumerative Aspects

219

(14)

Counting Proper Colorings

219

(5)

Chordal Graphs

224

(2)

A Hint of Perfect Graphs

226

(2)

Counting Acyclic Orientations (optional)

228

(1)

Exercises

229

(4)

Planar Graphs

233

(40)

Embeddings and Euler's Formula

233

(13)

Drawings in the Plane

233

(3)

Dual Graphs

236

Euler's Formula

241

(2)

Exercises

243

(3)

Characterization of Planar Graphs

246

(11)

Preparation for Kuratowski's Theorem

247

(1)

Convex Embeddings

248

(4)

Planarity Testing (optional)

252

(3)

Exercises

255

(2)

Parameters of Planarity

257

(16)

Coloring of Planar Graphs

257

(4)

Crossing Number

261

(5)

Surfaces of Higher Genus (optional)

266

(3)

Exercises

269

(4)

Edges and Cycles

273

(46)

Line Graphs and Edge-coloring

273

(13)

Edge-colorings

274

(5)

Characterization of Line Graphs (optional)

279

(3)

Exercises

282

(4)

Hamiltonian Cycles

286

(13)

Necessary Conditions

287

(1)

Sufficient Conditions

288

(5)

Cycles in Directed Graphs (optional)

293

(1)

Exercises

294

(5)

Planarity, Coloring, and Cycles

299

(20)

Tait's Theorem

300

(2)

Grinberg's Theorem

302

(2)

Snarks (optional)

304

(3)

Flows and Cycle Covers (optional)

307

(7)

Exercises

314

(5)

Additional Topics (optional)

319

(152)

Perfect Graphs

319

(30)

The Perfect Graph Theorem

320

(3)

Chordal Graphs Revisited

323

(5)

Other Classes of Perfect Graphs

328

(6)

Imperfect Graphs

334

(6)

The Strong Perfect Graph Conjecture

340

(4)

Exercises

344

(5)

Matroids

349

(29)

Hereditary Systems and Examples

349

(5)

Properties of Matroids

354

(4)

The Span Function

358

(2)

The Dual of a Matroid

360

(3)

Matroid Minors and Planar Graphs

363

(3)

Matroid Intersection

366

(3)

Matroid Union

369

(3)

Exercises

372

(6)

Ramsey Theory

378

(18)

The Pigeonhole Principle Revisited

378

(2)

Ramsey's Theorem

380

(3)

Ramsey Numbers

383

(3)

Graph Ramsey Theory

386

(2)

Sperner's Lemma and Bandwidth

388

(4)

Exercises

392

(4)

More Extremal Problems

396

(29)

Encodings of Graphs

397

(7)

Branchings and Gossip

404

(4)

List Coloring and Choosability

408

(5)

Partitions Using Paths and Cycles

413

(3)

Circumference

416

(6)

Exercises

422

(3)

Random Graphs

425

(27)

Existence and Expectation

426

(4)

Properties of Almost All Graphs

430

(2)

Threshold Functions

432

(4)

Evolution and Graph Parameters

436

(3)

Connectivity, Cliques, and Coloring

439

(3)

Martingales

442

(6)

Exercises

448

(4)

Eigenvalues of Graphs

452

(19)

The Characteristic Polynomial

453

(3)

Linear Algebra of Real Symmetric Matrices

456

(2)

Eigenvalues and Graph Parameters

458

(2)

Eigenvalues of Regular Graphs

460

(3)

Eigenvalues and Expanders

463

(1)

Strongly Regular Graphs

464

(3)

Exercises

467

(4)

Appendix A Mathematical Background

471

(22)

Sets

471

(4)

Quantifiers and Proofs

475

(4)

Induction and Recurrence

479

(4)

Functions

483

(2)

Counting and Binomial Coefficients

485

(4)

Relations

489

(2)

The Pigeonhole Principle

491

(2)

Appendix B Optimization and Complexity

493

(14)

Intractability

493

(3)

Heuristics and Bounds

496

(3)

NP-Completeness Proofs

499

(6)

Exercises

505

(2)

Appendix C Hints for Selected Exercises

507

(8)

General Discussion

507

(1)

Supplemental Specific Hints

508

(7)

Appendix D Glossary of Terms

515

(18)

Appendix E Supplemental Reading

533

(34)

Appendix F References

567

(2)

Author Index

569

(6)

Subject Index

575

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

PrefaceGraph theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. The design of this book permits usage in a one-semester introduction at the undergraduate or beginning graduate level, or in a patient two-semester introduction. No previous knowledge of graph theory is assumed. Many algorithms and applications are included, but the focus is on understanding the structure of graphs and the techniques used to analyze problems in graph theory.Many textbooks have been written about graph theory. Due to its emphasis on both proofs and applications, the initial model for this book was the elegant text by J.A. Bondy and US.R. Murty,Graph Theory with Applications(Macmillan/NorthHolland 1976). Graph theory is still young, and no consensus has emerged on how the introductory material should be presented. Selection and order of topics, choice of proofs, objectives, and underlying themes are matters of lively debate. Revising this book dozens of times has taught me the difficulty of these decisions. This book is my contribution to the debate. The Second EditionThe revision for the second edition emphasizes making the text easier for the students to learn from and easier for the instructor to teach from. There have not been great changes in the overall content of the book, but the presentation has been modified to make the material more accessible, especially in the early parts of the book. Some of the changes are discussed in more detail later in this preface; here I provide a brief summary. Optional material within non-optional sections is now designated by (*); such material is not used later and can be skipped. Most of it isintendedto be skipped in a one-semester course. When a subsection is marked "optional", the entire subsection is optional, and hence no individual items are starred. For less-experienced students, Appendix A has been added as a reference summary of helpful material on sets, logical statements, induction, counting arguments, binomial coefficients, relations, and the pigeonhole principle. Many proofs have been reworded in more patient language with additional details, and more examples have been added. More than 350 exercises have been added, mostly easier exercises in Chapters 1-7. There are now more than 1200 exercises. More than 100 illustrations have been added; there are now more than 400. In illustrations showing several types of edges, the switch to bold and solid edges instead of solid and dashed edges has increased clarity. Easier.problems are now grouped at the beginning of each exercise section, usable as warm-ups. Statements of some exercises have been clarified. In addition to hints accompanying the exercise statements, there is now an appendix of supplemental hints. For easier access, terms being defined are in bold type, and the vast majority of them appear in Definition items. For easier access, the glossary of notation has been placed on the inside covers. Material involving Eulerian circuits, digraphs, and Turyn's Theorem has been relocated to facilitate more efficient learning. Chapters 6 and 7 have been switched to introduce the idea of planarity earlier, and the section on complexity has become an appendix. The glossary has been improved to eliminate errors and to emphasize items more directly related to the text. FeaturesVarious features of this book facilitate students' efforts to understand the material. There is discussion of proof techniques, more than 1200 exercises of varying difficulty, more than 400 illustrations, and many examples. Proofs are presented in full in the text.Many undergraduates begin a course in graph theory with little exposure to proof techniques.

Amazon no longer offers textbook rentals. We do!

Introduction to Graph Theory

Introduction to Graph Theory

0130144002

Summary

Table of Contents

Supplemental Materials

Excerpts

Write a Review