Chapter 1 Fundamental Concepts 1
1.1 What Is a Graph？ 1
The Definition 1
Graphs as Models 3
Matrices and Isomorphism 6
Decomposition and Special Graphs 11
Exercises 14
1.2 Paths,Cycles,and Trails 19
Connection in Graphs 20
Bipartite Graphs 24
Eulerian Circuits 26
Exercises 31
1.3 Vertex Degrees and Counting 34
Counting and Bijections 35
Extremal Problems 38
Graphic Sequences 44
Exercises 47
1.4 Directed Graphs 53
Definitions and Examples 53
Vertex Degrees 58
Eulerian Digraphs 60
Orientations and Tournaments 61
Exercises 63
Chapter 2 Trees and Distance 67
2.1 Basic Properties 67
Properties of Trees 68
Distance in Trees and Graphs 70
Disjoint Spanning Trees(optional) 73
Exercises 75
2.2 Spanning Trees and Enumeration 81
Enumeration of Trees 81
Spanning Trees in Graphs 83
Decomposition and Graceful Labelings 87
Branchings and Eulerian Digraphs(optional) 89
Exercises 92
2.3 Optimization and Trees 95
Minimum Spanning Tree 95
Shortest Paths 97
Trees in Computer Science(optional) 100
Exercises 103
Chapter 3 Matchings and Factors 107
3.1 Matchings and Covers 107
Maximum Matchings 108
Hall's Matching Condition 110
Min-Max Theorems 112
Independent Sets and Covers 113
Dominating Sets(optional) 116
Exercises 118
3.2 Algorithms and Applications 123
Maximum Bipartite Matching 123
Weighted Bipartite Matching 125
Stable Matchings(optional) 130
Faster Bipartite Matching(optional) 132
Exercises 134
3.3 Matchings in General Graphs 136
Tutte's 1-factor Theorem 136
f-factors of Graphs(optional) 140
Edmonds'Blossom Algorithm(optional) 142
Exercises 145
Chapter 4 Connectivity and Paths 149
4.1 Cuts and Connectivity 149
Connectivity 149
Edge-connectivity 152
Blocks 155
Exercises 158
4.2 k-connected Graphs 161
2-connected Graphs 161
Connectivity of Digraphs 164
k-connected and k-edge-connected Graphs 166
Applications of Menger's Theorem 170
Exercises 172
4.3 Network Flow Problems 176
Maximum Network Flow 176
Integral Flows 181
Supplies and Demands(optional) 184
Exercises 188
Chapter 5 Coloring of Graphs 191
5.1 Vertex Colorings and Upper Bounds 191
Definitions and Examples 191
Upper Bounds 194
Brooks'Theorem 197
Exercises 199
5.2 Structure of k-chromatic Graphs 204
Graphs with Large Chromatic Number 205
Extremal Problems and Turán's Theorem 207
Color-Critical Graphs 210
Forced Subdivisions 212
Exercises 214
5.3 Enumerative Aspects 219
Counting Proper Colorings 219
Chordal Graphs 224
A Hint of Perfect Graphs 226
Counting Acyclic Orientations(optional) 228
Exercises 229
Chapter 6 Planar Graphs 233
6.1 Embeddings and Euler's Formula 233
Drawings in the Plane 233
Dual Graphs 236
Euler's Formula 241
Exercises 243
6.2 Characterization of Planar Graphs 246
Preparation for Kuratowski's Theorem 247
Convex Embeddings 248
Planarity Testing(optional) 252
Exercises 255
6.3 Parameters of Planarity 257
Coloring of Planar Graphs 257
Crossing Number 261
Surfaces of Higher Genus(optional) 266
Exercises 269
Chapter 7 Edges and Cycles 273
7.1 Line Graphs and Edge-coloring 273
Edge-colorings 274
Characterization of Line Graphs(optional) 279
Exercises 282
7.2 Hamiltonian Cycles 286
Necessary Conditions 287
Sufficient Conditions 288
Cycles in Directed Graphs(optional) 293
Exercises 294
7.3 Planarity,Coloring,and Cycles 299
Tait's Theorem 300
Grinberg's Theorem 302
Snarks(optional) 304
Flows and Cycle Covers(optional) 307
Exercises 314
Chapter 8 Additional Topics(optional) 319
8.1 Perfect Graphs 319
The Perfect Graph Theorem 320
Chordal Graphs Revisited 323
Other Classes of Perfect Graphs 328
Imperfect Graphs 334
The Strong Perfect Graph Conjecture 340
Exercises 344
8.2 Matroids 349
Hereditary Systems and Examples 349
Properties of Matroids 354
The Span Function 358
The Dual of a Matroid 360
Matroid Minors and Planar Graphs 363
Matroid Intersection 366
Matroid Union 369
Exercises 372
8.3 Ramsey Theory 378
The Pigeonhole Principle Revisited 378
Ramsey's Theorem 380
Ramsey Numbers 383
Graph Ramsey Theory 386
Sperner's Lemma and Bandwidth 388
Exercises 392
8.4 More Extremal Problems 396
Encodings of Graphs 397
Branchings and Gossip 404
List Coloring and Choosability 408
Partitions Using Paths and Cycles 413
Circumference 416
Exercises 422
8.5 Random Graphs 425
Existence and Expectation 426
Properties of Almost All Graphs 430
Threshold Functions 432
Evolution and Graph Parameters 436
Connectivity,Cliques,and Coloring 439
Martingales 442
Exercises 448
8.6 Eigenvalues of Graphs 452
The Characteristic Polynomial 453
Linear Algebra of Real Symmetric Matrices 456
Eigenvalues and Graph Parameters 458
Eigenvalues of Regular Graphs 460
Eigenvalues and Expanders 463
Strongly Regular Graphs 464
Exercises 467
Appendix A Mathematical Background 471
Sets 471
Quantifiers and Proofs 475
Induction and Recurrence 479
Functions 483
Counting and Binomial Coefficients 485
Relations 489
The Pigeonhole Principle 491
Appendix B Optimization and Complexity 493
Intractability 493
Heuristics and Bounds 496
NP-Completeness Proofs 499
Exercises 505
Appendix C Hints for Selected Exercises 507
General Discussion 507
Supplemental Specific Hints 508
Appendix D Glossary of Terms 515
Appendix E Supplemental Reading 533
Appendix F References 567
Author Index 569
Subject Index 575