## chapter 10**Graph 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 ...