Table of Content

1. Fundamental Concepts.
What Is a Graph? Paths, Cycles, and Trails. Vertex Degrees and Counting. Directed Graphs.

2. Trees and Distance.
Basic Properties. Spanning Trees and Enumeration. Optimization and Trees.

3. Matchings and Factors.
Matchings and Covers. Algorithms and Applications. Matchings in General Graphs.

4. Connectivity and Paths.
Cuts and Connectivity. k-connected Graphs. Network Flow Problems.

5. Coloring of Graphs.
Vertex Colorings and Upper Bounds. Structure of k-chromatic Graphs. Enumerative Aspects.

6. Planar Graphs.
Embeddings and Euler's Formula. Characterization of Planar Graphs. Parameters of Planarity.

7. Edges and Cycles.
Line Graphs and Edge-Coloring. Hamiltonian Cycles. Planarity, Coloring, and Cycles.

8. Additional Topics (Optional).
Perfect Graphs. Matroids. Ramsey Theory. More Extremal Problems. Random Graphs. Eigenvalues of Graphs.

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.
 

Salient Features

NEW - Appendix of Mathematical Background—Appendix A presents background material on logical statements, basic set theory, equivalence relations, and elementary counting.
Makes review material easily accessible for beginning students (Chapter 1 still discusses central proof techniques). Ex.___

NEW - Expanded and improved selection of exercises—Exercises have been added, especially easier exercises, and many exercises have been further clarified.
Enlarged selection of easier exercises provides greater encouragement for beginning students and makes the material useful for a broader range of students. Ex.___

NEW - Reorganization of material. Some material has been reorganized to provide a smoother development and clearer focus on essential material with optional material clearly designated or removed.
Facilitates more efficient learning by aiding instructors in designing courses and students in seeing what is important. Ex.___

NEW - Definitions more prominent. Terms being defined are in bold type and most important definitions occur in numbered items.
Makes definitions easier for students to find. Ex.___

NEW - Hints for selected exercises—More hints have been added as Appendix C.
Allows students to learn at their own pace; weaker students have more opportunity to be successful; stronger students have more opportunity to be stimulated. Ex.___

Logical organization—Concepts are introduced as needed, achieving a gradual increase in intellectual difficulty.
Allows students to find fundamental results in the early sections of chapters and to master elementary concepts in preparation for later applications. Ex.___

Additional topics—Final chapter is a bridge to advanced topics.
Provides supplementary reading for good students and flexibility in advanced courses. Ex.___

Over 400 illustrations.
Allows students to check their understanding of definitions and of steps in proofs. Ex.___

Over 1200 exercises—Ranging from relatively straightforward applications of ideas in the text to subtle problems requiring some ingenuity.
Helps students to understand the ideas of the course and to improve their presentation of coherent arguments. Ex.___

Graduation of exercises—Denotes easier exercises by (-), harder by (+), and particularly valuable or instinctive exercises by (!).
Aids instructor in selecting appropriate exercises and students in practicing for tests. Ex.___