Introduction to Graph Theory

Titlepage......Page 1
Contents......Page 5
Glossary of notation......Page 11
Preface......Page 12
The Definition ......Page 22
Graphs as Models ......Page 24
Matrices and Isomorphism ......Page 27
Decomposition and Special Graphs ......Page 32
Exercises ......Page 35
1.2 Paths, Cycles, and Trails ......Page 40
Connection in Graphs ......Page 41
Bipartite Graphs ......Page 45
Eulerian Circuits ......Page 47
Exercises ......Page 52
1.3 Vertex Degrees and Counting ......Page 55
Counting and Bijections ......Page 56
Extremal Problems ......Page 59
Graphic Sequences ......Page 65
Exercises ......Page 68
Definitions and Examples ......Page 74
Vertex Degrees ......Page 79
Eulerian Digraphs ......Page 81
Orientations and Tournaments ......Page 82
Exercises ......Page 84
 2.1 Basic Properties ......Page 88
Properties of Trees ......Page 89
Distance in Trees and Graphs ......Page 91
Disjoint Spanning Trees (optional) ......Page 94
Exercises ......Page 96
Enumeration of Trees ......Page 102
Spanning Trees in Graphs ......Page 104
Decomposition and Graceful Labelings ......Page 108
Branchings and Eulerian Digraphs (optional) ......Page 110
Exercises ......Page 113
Minimum Spanning Tree ......Page 116
Shortest Paths ......Page 118
Trees in Computer Science (optional) ......Page 121
Exercises ......Page 124
3.1 Matchings and Covers ......Page 128
Maximum Matchings ......Page 129
Hall\'s Matching Condition ......Page 131
Min-Max Theorems ......Page 133
Independent Sets and Covers ......Page 134
Dominating Sets (optional) ......Page 137
Exercises ......Page 139
Maximum Bipartite Matching ......Page 144
Weighted Bipartite Matching ......Page 146
Stable Matchings (optional) ......Page 151
Faster Bipartite Matching (optional) ......Page 153
Exercises ......Page 155
Tutte\'s one-factor Theorem ......Page 157
f -factors of Graphs (optional) ......Page 161
Edmonds\' Blossom Algorithm (optional) ......Page 163
Exercises ......Page 166
Connectivity ......Page 170
Edge-connectivity ......Page 173
Blocks ......Page 176
Exercises ......Page 179
2-connected Graphs ......Page 182
Connectivity of Digraphs ......Page 185
k-connected and k-edge-connected Graphs ......Page 187
Applications of Menger\'s Theorem ......Page 191
Exercises ......Page 193
Maximum Network Flow ......Page 197
Integral Flows ......Page 202
Supplies and Demands (optional) ......Page 205
Exercises ......Page 209
Definitions and Examples ......Page 212
Upper Bounds ......Page 215
Brooks\' Theorem ......Page 218
Exercises ......Page 220
5.2 Structure of k-chromatic Graphs ......Page 225
Graphs with Large Chromatic Number ......Page 226
Extremal Problems and Turan\'s Theorem ......Page 228
Color-Critical Graphs ......Page 231
Forced Subdivisions ......Page 233
Exercises ......Page 235
Counting Proper Colorings ......Page 240
Chordal Graphs ......Page 245
A Hint of Perfect Graphs ......Page 247
Counting Acyclic Orientations (optional) ......Page 249
Exercises ......Page 250
Drawings in the Plane ......Page 254
Dual Graphs ......Page 257
Exercises ......Page 276
Exercises ......Page 264
6.2 Characterization of Planar Graphs ......Page 267
Preparation for Kuratowski\'s Theorem ......Page 268
Convex Embeddings ......Page 269
Planarity Testing (optional) ......Page 273
Coloring of Planar Graphs ......Page 278
Crossing Number ......Page 282
Surfaces of Higher Genus (optional) ......Page 287
Exercises ......Page 290
 7.1 Line Graphs and Edge-coloring ......Page 294
Edge-colorings ......Page 295
Characterization of Line Graphs (optional) ......Page 300
Exercises ......Page 303
7.2 Hamiltonian Cycles ......Page 307
Necessary Conditions ......Page 308
Sufficient Conditions ......Page 309
Cycles in Directed Graphs (optional) ......Page 314
Exercises ......Page 315
Tait\'s Theorem ......Page 321
Grinberg\'s Theorem ......Page 323
Snarks (optional) ......Page 325
Flows and Cycle Covers (optional) ......Page 328
Exercises ......Page 335
8.1 Perfect Graphs ......Page 340
The Perfect Graph Theorem ......Page 341
Chordal Graphs Revisited ......Page 344
Other Classes of Perfect Graphs ......Page 349
Imperfect Graphs ......Page 355
The Strong Perfect Graph Conjecture ......Page 361
Exercises ......Page 365
Hereditary Systems and Examples ......Page 370
Properties of Matroids ......Page 375
The Span Function ......Page 379
The Dual of a Matroid ......Page 381
Matroid Minors and Planar Graphs ......Page 384
Matroid Intersection ......Page 387
Matroid Union ......Page 390
Exercises ......Page 393
The Pigeonhole Principle Revisited ......Page 399
Ramsey\'s Theorem ......Page 401
Ramsey Numbers ......Page 404
Graph Ramsey Theory ......Page 407
Sperner\'s Lemma and Bandwidth ......Page 409
Exercises ......Page 413
8.4 More Extremal Problems ......Page 417
Encodings of Graphs ......Page 418
Branchings and Gossip ......Page 425
List Coloring and Choosability ......Page 429
Partitions Using Paths and Cycles ......Page 434
Circumference ......Page 437
Exercises ......Page 443
8.5 Random Graphs ......Page 446
Existence and Expectation ......Page 447
Properties of Almost All Graphs ......Page 451
Threshold Functions ......Page 453
Evolution and Graph Parameters ......Page 457
Connectivity, Clique, and Coloring ......Page 460
Martingales ......Page 463
Exercises ......Page 469
8.6 Eigenvalues of Graphs ......Page 473
The Characteristic Polynomial ......Page 474
Linear Algebra of Real Symmetric Matrices ......Page 477
Eigenvalues and Graph Parameters ......Page 479
Eigenvalues of Regular Graphs ......Page 481
Eigenvalues and Expanders ......Page 484
Strongly Regular Graphs ......Page 485
Exercises ......Page 488
Sets ......Page 492
Quantifiers and Proofs ......Page 496
Induction and Recurrence ......Page 500
Functions ......Page 504
Counting and Binomial Coefficients ......Page 506
Relations ......Page 510
The Pigeonhole Principle ......Page 512
Intractability ......Page 514
Heuristics and Bounds ......Page 517
NP-Completeness Proofs ......Page 520
Exercises ......Page 526
General Discussion ......Page 528
Supplemental Specific Hints ......Page 529
Appendix D Glossary of Terms ......Page 536
Appendix E Supplemental Reading ......Page 554
Appendix F References ......Page 588
Author Index ......Page 590
Subject Index ......Page 596