Introduction to Graph Theory

COVER......Page 1
CONTENTS......Page 6
Preface......Page 13
1.1 What is a Graph?......Page 23
1.2 Paths, Cycles, and Trails......Page 41
1.3 Vertex Degrees and Counting......Page 56
1.4 Directed Graphs......Page 75
2.1 Basic Properties......Page 89
2.2 Spanning Trees and Enumeration......Page 103
2.3 Optimization and Trees......Page 117
3.1 Matchings and Covers......Page 129
3.2 Algorithms and Applications......Page 145
3.3 Matchings in General Graphs......Page 158
4.1 Cuts and Connectivity......Page 171
4.2 k-Connected Graphs......Page 183
4.3 Network Flow Problems......Page 198
5.1 Vertex Coloring and Upper Bounds......Page 213
5.2 Structure of k-chromatic Graphs......Page 226
5.3 Enumerative Aspects......Page 241
6.1 Embeddings and Euler's Formula......Page 255
6.2 Characterization of Planar Graphs......Page 268
6.3 Parameters of Planarity......Page 279
7.1 Line Graphs and Edge-coloring......Page 295
7.2 Hamiltonian Cycles......Page 308
7.3 Planarity, Colorings, and Cycles......Page 321
8.1 Perfect Graphs......Page 341
8.2 Matroids......Page 371
8.3 Ramsey Theory......Page 400
8.4 More Extremal Problems......Page 418
8.5 Random Graphs......Page 447
8.6 Eigenvalues of Graphs......Page 474
Appendix A: Mathematical Background......Page 493
Appendix B: Optimization and Complexity......Page 515
Appendix C: Hints for Selected Exercises......Page 529
Appendix D: Glossary of Terms......Page 537
Appendix E: Supplemetal Reading......Page 555
Appendix F: References......Page 559
Author Index......Page 591
Subject Index......Page 597
Solution Manual......Page 612
CH.1......Page 616
CH.2......Page 657
CH.3......Page 687
CH.4......Page 709
CH.5......Page 733
CH.6......Page 763
CH.7......Page 785
CH.8......Page 815