Graph theory has long been recognized as one of the more useful mathematical subjects for the computer science student to master. The approach that is natural to computer science is the algorithmic one; our interest is not so much in the existence proofs or enumeration techniques as it is in finding efficient algorithms for solving relevant problems or, alternatively, in showing evidence that no such algorithmexists. Although algorithmic graph theory was started by Euler, if not earlier, its development in the last ten years has been dramatic and revolutionary. Much of the material in Chapters 3, 5, 6, 8, 9, and 10 is less than ten years old.

This book is meant to be a textbook for an upper-level undergraduate, or a graduate course. It is the result of my experience in teaching such a course numerous times, since 1967, at Harvard, the Weizmann Institute of Science, Tel-Aviv University, the University of California at Berkeley, and the Technion. There is more than enough material for a one-semester course; I am sure that most teachers will have to omit parts of the book. If the course is for undergraduates, Chapters 1 to 5 provide enough material, and even then, the teacher may choose to omit a few sections, such as 2.6, 2.7, 3.3, and 3.4. Chapter 7 consists of classical nonalgorithmic studies of planar graphs, which are necessary in order to understand the tests of planarity, described in Chapter 8; it may be assigned as a preparatory reading assignment.