第1章　基本概念1
1.1　什么是图1
定义1
图模型3
矩阵和同构6
分解和特殊图11
习题14
1.2　路径、环和迹19
图的连通性20
二部图24
欧拉回路26
习题31
1.3　顶点度和计数34
计数和双射35
极值问题38
图序列44
习题47
1.4　有向图53
定义和例子53
顶点度58
欧拉有向图60
定向和竞赛图61
习题63
第2章　树和距离67
2.1　基本性质67
树的性质68
树和图中的距离70
不相交生成树（选学）73
习题75
2.2　生成树和枚举81
树的枚举81
图的生成树83
分解和优美标记87
分叉和欧拉有向图（选学）89
习题92
2.3　最优化和树95
最小生成树95
最短路径97
计算机科学中的树（选学）100
习题103
第3章　匹配和因子107
3.1　匹配和覆盖107
最大匹配108
Hall匹配条件110
最小–最大定理112
独立集和覆盖113
支配集（选学）116
习题118
3.2　算法和应用123
最大二部匹配123
加权二部匹配125
稳定匹配（选学）130
快速二部匹配（选学）132
习题134
3.3　一般图中的匹配136
Tutte 1-因子定理136
图的f-因子（选学）140
Edmonds开花算法（选学）142
习题145
第4章　连通度和路径149
4.1　割和连通度149
连通度149
边–连通度152
块155
习题158
4.2　k–连通图161
2–连通图161
有向图的连通度164
k–连通图和k–边连通图166
Menger定理的应用170
习题172
4.3　网络流问题176
最大网络流176
整数流181
供应和需求（选学）184
习题188
第5章　图的着色191
5.1　顶点着色和上界191
定义和实例191
上界194
Brooks定理197
习题199
5.2　k–色图的结构204
大色数图205
极值问题和Turán定理207
颜色–临界图210
强制细分212
习题214
5.3　计数方面的问题219
真着色的计数219
弦图224
完美图点滴226
无环定向的计数（选学）228
习题229
第6章　可平面图233
6.1　嵌入和欧拉公式233
平面作图233
对偶图236
欧拉公式241
习题243
6.2　可平面图的特征246
Kuratowski定理的预备知识247
凸嵌入248
可平面性测试（选学）252
习题255
6.3　可平面性的参数257
可平面图的着色257
交叉数261
具有更高亏格的表面（选学）266
习题269
第7章　边和环273
7.1　线图和边着色273
边着色274
线图的特征（选学）279
习题282
7.2　哈密顿环286
必要条件287
充分条件288
有向图中的环（选学）293
习题294
7.3　可平面性、着色和环299
Tait定理300
Grinberg定理302
鲨鱼图（选学）304
流和环覆盖（选学）307
习题314
第8章　其他主题（选学）319
8.1　完美图319
完美图定理320
弦图的再研究323
其他类型的完美图328
非完美图334
强完美图猜想340
习题344
8.2　拟阵349
遗传系统和示例349
拟阵的性质354
生成函数358
拟阵的对偶性360
拟阵的子式和可平面图363
拟阵的交366
拟阵的并369
习题372
8.3　Ramsey理论378
鸽巢原理的再研究378
Ramsey定理380
Ramsey数383
关于图的Ramsey理论386
Sperner引理和带宽388
习题392
8.4　其他极值问题396
图的编码397
分叉和流言404
序列着色和可选择性408
使用路径和环的划分413
周长416
习题422
8.5　随机图425
存在性和期望值426
几乎所有图均具有的性质430
阈值函数432
演变和图参数436
连通度、团和着色439
鞅442
习题448
8.6　图的特征值452
特征多项式453
实对称矩阵的线性代数456
特征值和图参数458
正则图的特征值460
特征值和扩张图463
强正则图464
习题467
附录A　数学基础471
附录B　最优化和复杂度493
附录C　部分习题的提示507
附录D　术语表515
附录E　补充阅读材料533
附录F　参考文献567
作者索引569
术语索引575
Contents
Preface xi
Chapter 1 Fundamental Concepts
1.1 What Is a Graph?
The Definition, 1
Graphs as Models, 3
Matrices and Isomorphism, 6
Decomposition and Specia] 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
2.1 Basic Properties
Properties of Trees, 68
Distance in Trees and Graphs, 70
Disjoint Spanning Trees (optional), 73
Exercises, 75
2.2 Spanning Trees and Enumeration
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
Minimum Spanning Tree, 95
Shortest Paths, 97
Trees in Computer Science (optional)，100
Exercises, 103
Chapter 3 Matchings and Factors
3.1 Matchings and Covers
Maximum Matchings, 108
Hall's Matching Condition
Min-Max Theorems, 112
Independent Sets and Covers, 113
Dominating Sets (optional), 116
Exercises, 118
3.2 Algorithms and Applications
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
Tutte's 1-factor Theorem, 136
f-factors of Graphs (optional), 140
Edmonds' Blossom Algorithm (optional)
Exercises, 145
Chapter 4 Connectivity and Paths
4.1 Cuts and Connectivity
Connectivity, 149
Edge-connectivity,152
Blocks, 155
Exercises, 158
4.2 k-connected Graphs
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
Maximum Network Flow, 176
Integral Flows, 181
Supplies and Demands (optional), 184
Exercises, 188
Chapter 5 Coloring of Graphs
5.1 Vertex Colorings and Upper Bounds
Definitions and Examples, 191
Upper Bounds, 194
Brooks' Theorem, 197
Exercises, 199
5.2 Structure of k-chromatic Graphs
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
Counting Proper Colorings, 219
Chordal Graphs, 224
A Hint of Perfect Graphs, 226
Counting Acyclic Orientations (optional), 228
Exercises, 229
Chapter 6 Planar Graphs
6.1 Embeddings and Euler's Formula
Drawings in the Plane, 233
Dual Graphs, 236
Euler's Formula, 241 255
Exercises, 243
6.2 Characterization of Planar Graphs
Preparation for Kuratowski's Theorem, 247
Convex Embeddings, 248
Planarity Testing (optional), 252
Exercises, 255
6.3 Parameters of Planarity
Coloring of Planar Graphs, 257
Crossing Number, 261
Surfaces of Higher Genus (optional), 266
Exercises, 269
Chapter 7 Edges and Cycles
7.1 Line Graphs and Edge-coloring
Edge-colorings, 274
Characterization of Line Graphs (optional), 279
Exercises, 282
7.2 Hamiltonian Cycles
Necessary Conditions, 287
Sufficient Conditions, 288
Cycles in Directed Graphs (optional),293
Exercises, 294
7.3 Planarity, Coloring, and Cycles
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
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
Appendix B Optimization and Complexity
Appendix C Hints for Selected Exercises
Appendix D Glossary of Terms
Appendix E Supplemental Reading
Appendix F References
Author Index
Subject Index