Discrete Structures, Logic, and Computability, 4th Edition

chapter 10Graph Theory

An early-morning walk is a blessing for the whole day.

—Henry David Thoreau (1817–1862)

In Section 1.4 we introduced some elementary facts about graphs that were useful in subsequent chapters. In this chapter, we’ll expand the discussion and introduce some important areas of graph theory. In the first three sections, we’ll introduce the basic types of graphs along with some results about the structure of graphs. The rest of the chapter is devoted to introducing the matching problem, two famous traversal problems, the planarity problem, and the coloring problem.

10.1 Definitions and Examples

For the most part, we will refer to the basic notions and notations for graphs presented in Section 1.4. We’ll start by introducing ...