ABSTRACT
One way to judge the importance of a branch of mathematics is by the variety of unrelated problems to which it can be applied. By this measure, the subject of this chapter is surely one of the most important in discrete mathematics. To illustrate, we begin by presenting three quite different problems to which graph theory can be applied. One of these is a children’s puzzle; one is a problem on the properties of sequences; and the last is a common problem in computer science. (By the way, the first example in this book (in the Prologue) also was an example of graph theory.)
In presenting these three problems we’ll introduce informally some of the terminology of graph theory. We think you will understand these examples without much elaboration of the terminology. Later in this section we’ll formalize the terminology used in the examples as well as some of the other terminology of graph theory.
