For undergraduate or graduate courses in Graph Theory in
departments of mathematics or computer science.
This text offers a comprehensive and coherent introduction
to the fundamental topics of graph theory. It includes basic algorithms
and emphasizes the understanding and writing of proofs about graphs.
Thought-provoking examples and exercises develop a thorough understanding
of the structure of graphs and the techniques used to analyze problems.
NEWAppendix of Mathematical BackgroundAppendix
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).
NEWExpanded and improved selection of
exercisesExercises 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.
NEWReorganization 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.
Aids instructors in designing courses and students in
seeing what is important.
NEWDefinitions in bold. Terms being
defined are in bold type and most important definitions occur in numbered
Makes definitions easier for students to find.
NEWHints for selected exercisesMore
hints have been added in an appendix.
Allows students to learn at their own pace; weaker students
have more opportunity to be successful; stronger students have more
opportunity to be stimulated.
Logical organizationConcepts 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.
Additional topicsFinal chapter is a bridge to
Provides supplementary reading for good students and
flexibility in advanced courses.
Over 300 illustrations.
Allows students to check their understanding of definitions
and of steps in proofs.
Approximately 1000 exercisesRanging 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.
Graduation of exercisesMarks easier exercises
by (-), harder by (+), and particularly valuable or instinctive exercises
Aids instructor in selecting appropriate exercises and
students in practicing for tests.
1. Fundamental Concepts.
2. Trees and Distance.
3. Matchings and Factors.
4. Connectivity and Paths.
5. Graph Coloring.
6. Planar Graphs.
7. Edges and Cycles.
8. Additional Topics.
Appendix A. Mathematical Background.
Appendix B. Hints to Selected Exercises.
Appendix C. Glossary.